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

در علم حساب و برنامه نویسی کامپیوتر الگوریتم تعمیم یافته اقلیدس تعمیمی بر الگوریتم اقلیدس است که در کنار محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح a,b ضرایب قضیه بزو را هم محاسبه می‌کند(x,y اعداد صحیح اند): 
 
همچنین می‌توان بدون هزینهٔ اضافی خارج قسمت a,b را با بزرگترین مقسوم علیه مشترک محاسبه کرد.
الگوریتم تعمیم یافته اقلیدس به الگوریتمی بسیار مشابه به الگوریتمی برای محاسبه بزرگترین مقسوم علیه مشترک چندجمله ای و ضرایب قضیه بزو از دو چندجمله‌ای با یک متغیر، ارجاع دارد. 
الگوریتم تعمیم یافته اقلیدس زمانی که a و b نسبت به هم اولند مفید تر است. چون x برابر وارون ضربی پیمانه‌ای a به پیمانه b و y برابر وارون ضربی پیمانه‌ای b به پیمانه a است. در الگوریتم اقلیدس برای چندجمله‌ای می‌توان وارون ضربی را در بسط‌های میدان جبری محاسبه کرد. که از آن نتیجه می‌شود هردو نوع الگوریتم اقلیدسی تعمیم یافته (معمولی و چندجمله‌ای) کاربردی گسترده در رمزنگاری دارند. به خصوص در محاسبه وارون ضربی پیمانه‌ای در روش RSA یک گام ضروریست. 
 

شبه‌کد

برای پیاده‌سازی الگوریتمی که در بالا ذکر شد،اولاً باید توجه داشت که در هر مرحله تنها نیاز به نگهداری دو مقدار نهایی متغیرهای شاخص‌گذاری شده، هست. بنابراین برای صرفه جویی در حافظه هر متغیر شاخص‌گذاری شده باید با تنها دو متغیر جایگزین شود. 
برای راحتی کار در الگوریتم زیر(و بقیهٔ الگوریتم‌ها در این مقاله) از مقداردهی موازی استفاده می‌شود.در زبانهای برنامه نویسی که از مقداردهی موازی پشتیبانی نمی‌کنند، باید اینکار را با کمک یک متغیر کمکی شبیه سازی کرد.
برای مثال 
(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 غیر اول هست.

بسط‌های میدان جبری ساده

الگوریتم پیشرفتهٔ اقلیدس همچنین ابزار اصلی برای محاسبهٔ وارون ضربی در تعمیم‌های میدان جبری ساده هست.یک نمونهٔ مهم که به‌طور گسترده‌ای در رمزنگاری و نظریه کدگذاری استفاده می‌شود میدان‌های جبری با اندازه (order) غیر اول هست.
در واقع اگر p یک عدد اول باشد و q = pd، میدان با اندازه(order) q یک تعمیم سادهٔ جبری از میدان اول p عضو ، هست، که توسط یک ریشهٔ معادله چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است. 
یک بسط سادهٔ جبری L از یک میدان K که توسط ریشه یک چندجمله‌ای کاهش ناپذیر از درجه d ساخته شده‌است، ممکن است توسط حلقهٔ خارج قسمت‌های  به‌طور یکتا شناسایی شود، و اعضایش در یک رابطهٔ یک به یک و و پوشا با چندجمله‌ای‌هایی با درجات کمتر از d هستند.عمل جمع در L همان جمع چندجمله‌ای ها است.عمل ضرب در L باقی‌ماندهٔ تقسیم اقلیدسی بر، p حاصلضرب چندجمله ای‌ها است.بنابراین برای تکمیل اعمال حسابی در L تنها کافیست نحوهٔ محاسبهٔ وارون ضربی را تعریف کنیم.که آن با استفاده از الگوریتم تعمیم یافتهٔ اقلیدسی انجام می‌شود. 
این الگوریتم بسیار شبیه الگوریتمی است که در بالا برای محاسبهٔ وارون ضربی پیمانه‌ای بیان شده‌است.در اینجا دو تفاوت مهم وجود دارد:اولاً اینکه به خط آخر نیازی نیست، چون ضریب بزو همیشه یک درجه کمتر از d دارد. 
دوم اینکه ب.م.م ای که بدست آمده‌است، وقتی که چندجمله‌ای‌های ورودی نسبت به هم اولند، ممکن هست هر عضو غیرصفری از K باشند، بنابراین ضریب بزو (یک چندجمله‌ای با درجهٔ مثبت) باید در وارون این عضو از K ضرب شود. 
در شبه کد زیر p یک چندجمله‌ای از درجه بزرگتر از یک هست و a یک چندجمله‌ای هست.علاوه بر این div یک تابع کمکی است که خارج قسمت تقسیم اقلیدسی را حساب می‌کند. 
 '''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