الگوریتم تعمیم‌یافته اقلیدس

در الگوریتم اقلیدسی معمولی فقط باقی‌مانده‌ها نگاه داشته می‌شوند و خارج قسمت استفاده نمی‌شود. اما در الگوریتم تعمیم یافته خارج قسمت‌های متوالی استفاده می‌شوند. به‌طور دقیقتر در الگوریتم تعمیم یافته که a، b را به عنوان ورودی می‌گیرد، دنبالهٔ  ${\displaystyle q_{1},\ldots ,q_{k}}$

${\displaystyle {\begin{array}{l}r_{0}=a\\r_{1}=b\\\ldots \\r_{i+1}=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\\\ldots \end{array}}}$

مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که  ${\displaystyle r_{i+1}}$

${\displaystyle {\begin{array}{l}s_{0}=1\qquad s_{1}=0\\t_{0}=0\qquad t_{1}=1\\\ldots \\s_{i+1}=s_{i-1}-q_{i}s_{i}\\t_{i+1}=t_{i-1}-q_{i}t_{i}\\\ldots \end{array}}}$

در این الگوریتم هم وقتی ${\displaystyle r_{k+1}=0}$

• ${\displaystyle r_{k}}$
   بزرگترین مقسوم علیه برای دو ورودی  ${\displaystyle a=r_{0}}$
   و ${\displaystyle b=r_{1}.}$
   است.
• ضرایب بزو هم که برابر ${\displaystyle s_{k}}$
  و ${\displaystyle t_{k},}$
   در رابطهٔ زیر صدق می‌کنند:

${\displaystyle GCD(a,b)=r_{k}=as_{k}+bt_{k}}$

• خارج قسمت تقسیم a و b بر بزرگترین مقسوم علیه مشترکشان به این صورت است:

${\displaystyle s_{k+1}=\pm {\frac {b}{GCD(a,b)}}}$

${\displaystyle |s_{k}|<{\frac {b}{GCD(a,b)}}\quad {\text{and}}\quad |t_{k}|<{\frac {a}{GCD(a,b)}}.}$

 

که این یعنی جفت ضرایب بزو که از این الگوریتم به دست می‌آیند یکی از کمترین جفت ضرایب بزو هستند.

جدول زیر رویه الگوریتم تعمیم یافته اقلیدسی را برای46 و240 را نشان می‌دهد. بزرگترین مقسوم علیه مشترک برابر ۲ است. محاسبه در ستون ۶ متوقف می‌شود، چون باقی‌مانده صفر می‌شود. ضرایب بزو هم در دو ستون آخر از سطر آخرند. تحقیق رابطه -9*240+47*46=2 راحت است. و سرانجام -120 و 23 بدون توجه به علامت برابر تقسیم ۲۴۰ و ۴۶ بر بزرگترین مقسوم علیه مشترک یعنی ۲ هستند

چون  ${\displaystyle 0\leq r_{i+1}<|r_{i}|,}$

چون ${\displaystyle r_{i+1}=r_{i-1}-r_{i}q_{i},}$

${\displaystyle a=r_{0}}$

ماتریس زیر را در نظر بگیرید

${\displaystyle A_{i}={\begin{pmatrix}s_{i-1}&s_{i}\\t_{i-1}&t_{i}\end{pmatrix}}\,.}$

رابطهٔ بازگشی را به شکل ماتریسی می‌نویسیم

${\displaystyle A_{i+1}=A_{i}\,.\,{\begin{pmatrix}0&1\\1&-q_{i}\end{pmatrix}}\,.}$

ماتریس ${\displaystyle A_{1}}$

برای یک چندجمله‌ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). اولین تفاوت در تقسیم اقلیدسی و الگوریتم، جایگذاری ${\displaystyle \deg r_{i+1}<\deg r_{i}.}$

${\displaystyle as+bt=\gcd(a,b)}$

${\displaystyle \deg s<\deg b-\deg(\gcd(a,b)),\quad \deg t<\deg a-\deg(\gcd(a,b)).}$

تفاوت سوم در این است که بزرگترین مقسوم علیه مشترک فقط به صورت ضرب یک ثابت غیر صفر تعریف می‌شود. راه‌های مختلفی برای تعریف بزرگترین مقسوم علیه مشترک به صورت غیر مبهم وجود دارد. در ریاضیات معمولاً به چندجمله‌ای که ب.م.م همهٔ ضریب‌هایش یک هست نیاز است. برای رسیدن به این مقصود کافیست هر خروجی را بر ضریب بزرگترین توان ${\displaystyle r_{k}.}$

${\displaystyle as+bt=\operatorname {Res} (a,b),}$

 که ${\displaystyle \operatorname {Res} (a,b)}$

برای پیاده‌سازی الگوریتمی که در بالا ذکر شد،اولاً باید توجه داشت که در هر مرحله تنها نیاز به نگهداری دو مقدار نهایی متغیرهای شاخص‌گذاری شده، هست. بنابراین برای صرفه جویی در حافظه هر متغیر شاخص‌گذاری شده باید با تنها دو متغیر جایگزین شود. برای راحتی کار در الگوریتم زیر(و بقیهٔ الگوریتم‌ها در این مقاله) از مقداردهی موازی استفاده می‌شود.در زبانهای برنامه نویسی که از مقداردهی موازی پشتیبانی نمی‌کنند، باید اینکار را با کمک یک متغیر کمکی شبیه سازی کرد.

برای مثال

(old_r, r) := (r, old_r - quotient *r)

برابر هست با

prov := r;
 r := old_r - quotient * prov;
 old_r := prov;

و مشابهاً برای بقیهٔ استفاده‌ها از مقداردهی موازی هم باید چنین کاری کرد.که اینکار به کد زیر می انجامد:

'''function''' extended_gcd(a, b)
     s := 0;    old_s := 1
     t := 1;    old_t := 0
     r := b;    old_r := a
     '''while''' r ≠ 0
         quotient := old_r '''div''' r
         (old_r, r) := (r, old_r - quotient *r)
         (old_s, s) := (s, old_s - quotient *s)
         (old_t, t) := (t, old_t - quotient *t)       
     '''output''' "Bézout coefficients:", (old_s, old_t)
     '''output''' "greatest common divisor:", old_r
     '''output''' "quotients by the gcd:", (t, s)

باید به این نکته توجه داشت که خارج قسمت‌های a و b در تقسیم بر ب.م.م، که خروجی این الگوریتم هست، ممکن هست علامت نادرستی داشته باشند. رفع این مشکل در انتهای محاسبات بسیار ساده هست، اما در اینجا به دلیل سادگی کد بیان نشده‌است. مشاب‌ها اگر یکی از دو مقدار a یا b منفی و دیگری صفر باشد، ب.م.م، که خروجی این الگوریتم هست، منفی می‌شود و باید علامت خروجی تغییر کند.

الگوریتم تعمیم یافتهٔ اقلیدس وسیلهٔ اصلی برای محاسبهٔ وارون ضربی در ساختارهای پیمانه‌ای هست و اغلب در حساب پیمانه‌ای اعداد صحیح و تعمیم‌های میادین جبری به کار می‌آید.یک نمونهٔ مهم از مورد آخر میدان‌های متناهی با order غیر اول هست.

اگر n یک عدد صحیح مثبت باشد، حلقهٔ Z/nZ ممکن هست توسط مجموعه {0, 1, ..., n} از باقی‌مانده‌های تقسیم اقلیدسی بر n قابل شناسایی باشد،عمل جمع و ضرب همان محاسبه ی، باقی‌ماندهٔ نتیجهٔ جمع و ضرب اعداد صحیح، بر n هست.یک عضو از Z/nZ یک وارون ضربی دارد(اگر چنین باشد، به آن unit میگویند) اگر نسبت به n اول باشد.در حالت خاص اگر n اول باشد a وارون ضربی دارد،اگر مخالف صفر باشد(باقی‌مانده اش بر n).بنابراین Z/nZ یک میدان هست اگر و تنها اگر n اول باشد. قضیه بزو بیان می‌کند که a و n نسبت به هم اولند اگر و تنها اگر اعداد صحیحی مانند s و t وجود داشته باشند که

${\displaystyle ns+at=1}$

که اگر از دوطرف بر n باقی‌مانده بگیریم:

${\displaystyle at=1\mod n.}$

بنابراین t یا، به‌طور دقیقتر، باقی‌ماندهٔ تقسیم t بر n، همان وارون ضربی a در پیمانهٔ n هست. برای تطبیق دادن الگوریتم تعمیم یافتهٔ اقلیدس به نحوی که این مسئله را حل کند، باید در نظر داشته باشیم که نیازی به محاسبهٔ ضرایب بزو ی n نیست.همچنین برای اینکه نتیجه مثبت و کمتر از n باشد، باید از این موضوع که t همواره در رابطهٔ |t| < n صدق می‌کند،استفاده کرد. اگر t <0 در انتهای کار می‌توان با جمع کردن آن با n آن را مثبت کرد.این تغییرات را در شبه کد زیر آورده ایم که در آن n یک عدد صحیح بزرگتر از یک هست.

 '''function''' inverse(a, n)
     t := 0;     newt := 1;    
     r := n;     newr := a;    
     '''while''' newr ≠ 0
         quotient := r '''div''' newr
         (t, newt) := (newt, t - quotient * newt) 
         (r, newr) := (newr, r - quotient * newr)
     '''if''' r> 1 then '''return''' "a is not invertible"
     '''if''' t <0 '''then''' t := t + n
     '''return''' t

الگوریتم پیشرفتهٔ اقلیدس همچنین ابزار اصلی برای محاسبهٔ وارون ضربی در تعمیم‌های میدان جبری ساده هست.یک نمونهٔ مهم که به‌طور گسترده‌ای در رمزنگاری و نظریه کدگذاری استفاده می‌شود میدان‌های جبری با اندازه (order) غیر اول هست.

در واقع اگر p یک عدد اول باشد و q = pd، میدان با اندازه(order) q یک تعمیم سادهٔ جبری از میدان اول p عضو ، هست، که توسط یک ریشهٔ معادله چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است. یک بسط سادهٔ جبری L از یک میدان K که توسط ریشه یک چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است، ممکن است توسط حلقهٔ خارج قسمت‌های ${\displaystyle K[X]/\langle p\rangle ,}$

 '''function''' inverse(a, p)
     t := 0;     newt := 1;    
     r := p;     newr := a;    
     '''while''' newr ≠ 0
         quotient := r '''div''' newr
         (r, newr) := (newr, r - quotient * newr)
         (t, newt) := (newt, t - quotient * newt) 
     '''if''' degree(r)> 0 then 
         '''return''' "Either p is not irreducible or a is a multiple of p"
     '''return''' (1/r) * t

برای مثال اگر چندجمله‌ای که برای تعریف میدان متناهی  GF(28)  بکار میرود p = x8 + x4 + x3 + x + 1 باشد و a = x6 + x4 + x + 1  عضوی باشد که وارونش مطلوب ماست، نتایج اجرای هر مرحله از الگوریتم در جدول زیر مشاهده می‌شود.با توجه به اینکه میدان با order 2n برای هر عضو z عضو -z = z  و z + z = 0را هم دارد.توجه کنید که 1 تنها عضو غیرصفری از GF(2)هست که برایش تغییرات در خط آخر شبه کد مورد نیاز نبوده‌است.

بنابراین وارون مطلوب x7 + x6 + x3 + xهست، و می‌شود با انجام عمل ضرب دو عضو در هم و گرفتن باقی‌مانده بر pبه صحت آن پی برد.

ما می‌توانیم در موردی که تعداد اعداد بیش از دو تا هست، به‌طور پشت سر هم(دو تا باهم و سپس حاصل آن‌ها با عدد بعدی) از این الگوریتم استفاده کنیم.اول باید اثبات کنیم که ${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$

${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})=\gcd(a_{1},\,\gcd(a_{2},\,\gcd(a_{3},\dots ,\gcd(a_{n-1}\,,a_{n})))\dots ),}$

که همان چیز مورد انتظار ما هست.

• Knuth، Donald. هنر برنامه‌نویسی رایانه. Addison-Wesley. Volume 2, Chapter 4.
• توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8)