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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علم حساب و برنامه نویسی کامپیوتر الگوریتم تعمیم یافته اقلیدس تعمیمی بر الگوریتم اقلیدس است که در کنار محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح a,b ضرایب قضیه بزو را هم محاسبه می کند(x,y اعداد صحیح اند): ax + by = \gcd(a, b). همچنین می‌توان بدون هزینهٔ اضافی خارج قسمت a,b را با بزرگترین مقسوم علیه مشترک محاسبه کرد.

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

توضیح الگوریتم[ویرایش]

در الگوریتم اقلیدسی معمولی فقط باقی‌مانده ها نگاه داشته میشوند و خارج قسمت استفاده نمی‌شود. اما در الگوریتم تعمیم یافته خارج قسمتهای متوالی استفاده میشوند. به طور دقیقتر در الگوریتم تعمیم یافته که a ، b را به عنوان ورودی می‌گیرد، دنبالهٔ  q_1,\ldots, q_k از خارج قسمتها و دنبالهٔ  r_0,\ldots, r_{k+1} از باقی‌مانده‌ها را شامل میشود.


\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\le r_{i+1} <|r_i|\\
\ldots
\end{array}

مهمترین ویژگی تقسیم اقلیدسی نامساوی سمت راست است که  r_{i+1} را متفاوت از  r_{i-1} و r_{i} تعریف می‌کند. وقتی باقی‌مانده به صفر رسید محاسبه متوقف میشود، بزرگترین مقسوم علیه مشترک آخرین باقی‌مانده غیر صفر است. الگوریتم تعمیم یافته اقلیدسی روشی مشابه دارد با این تفاوت که دو دنبالهٔ زیر نیز به آن اضافه میشود:


\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}

در این الگوریتم هم وقتی r_{k+1}=0 میشود کار الگوریتم به اتمام می‌رسد.

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

GCD(a,b)=r_{k}=as_k+bt_k

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

s_{k+1}=\pm\frac{b}{GCD(a,b)} و t_{k+1}=\pm\frac{a}{GCD(a,b)} به علاوه اگر a و b هردو مثبت باشند داریم:

|s_k|<\frac{b}{GCD(a,b)}\quad \text{and} \quad |t_k|<\frac{a}{GCD(a,b)}.

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

مثال[ویرایش]

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

index i quotient qi-1 Remainder ri si ti
0 240 1 0
1 46 0 1
2 240 ÷ 46 = 5 240 − 5 × 46 = 10 1 − 5 × 0 = 1 0 - 5 × 1 = -5
3 46 ÷ 10 = 4 46 − 4 × 10 = 6 0 − 4 × 1 = -4 1 - 4× -5 = 21
4 10 ÷ 6 = 1 10 − 1 × 6 = 4 1 − 1 ×-4 =5 -5 - 1 × 21 = -26
5 6 ÷ 4 = 1 6 − 1 × 4 = 2 -4 − 1 × 5 = -9 21 - 1 × -26 = 47
6 4 ÷ 2 = 2 4 − 2 × 2 = 0 5 − 2 × -9 = 23 -26 - 2 × 47 =-120

اثبات[ویرایش]

چون   0\le r_{i+1}<|r_i|,  و دنبالهٔ باقی‌مانده ها یک دنبالهٔ نزولی غیر منفی است در نتیجه باید حتماً با  r_{k+1}=0.  متوقف شود. این نشان میدهد که الگوریتم متوقف میشود و کار به اتمام می‌رسد.

چون  r_{i+1}= r_{i-1} - r_i q_i, درنتیجه بزرگترین مقسوم علیه مشترک  (r_{i-1}, r_i) و  (r_{i}, r_{i+1}) برابر است. که از ان نتیجه می شود بزرگترین مقسوم علیه مشترک  a=r_0, b=r_1  برابر است با بزرگترین مقسوم علیه مشترک  r_k, r_{k+1}=0.  وهمچنین نشان میدهد که  r_k  بزرگترین مقسوم علیه مشترک a و b است که آن را d می‌نامیم.

 a=r_0 و  b=r_1,  که برای i=0,1داریم: as_i+bt_i=r_i  برای هر i رابطهٔ بازگشتی خطی  برقرار است بخصوص برای i=k که as_k+bt_k=r_k,  نشان میدهیم که  (s_k, t_k)  ضرایب بزو اند. 

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

A_i=\begin{pmatrix}
s_{i-1} & s_i\\
t_{i-1} & t_i
\end{pmatrix} \,.

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

A_{i+1} = A_i
\,.\,
\begin{pmatrix}
0 & 1\\
1 & -q_i
\end{pmatrix} \,.

ماتریس  A_1 ماتریس واحد است و دترمینان آن برابر ۱ است. دترمینان ماتریس سمت راست برابر -1 است که نتیجه میشود دترمینان  A_i برابر (-1)^{i-1}. است و برای حالت خاص i=k+1 داریم  s_k t_{k+1}-t_k s_{k+1} = (-1)^k.  که نشان میدهد  s_{k+1} و  t_{k+1} نسبت بهم اولند. رابطهٔ as_{k+1}+bt_{k+1}=0 که در بالا اثبات شد و لم اقلیدس نشان میدهد که  s_{k+1} مقسوم علیه b و  t_{k+1} مقسوم علیه a اند. چون آنها نسبت بهم اولاً بدون در نظر گرفتن علامتشان برابر خارج قسمت تقسیم a و b بر d میشوند.

الگوریتم اقلیدسی برای چندجمله ای[ویرایش]

برای یک چند جمله ای با ضریب در یک میدان همه چیز مشابه حالت قبل است (تقسیم اقلیدسی، قضیه بزو، و تعمیم الگوریتم اقلیدس). اولین تفاوت در تقسیم اقلیدسی و الگوریتم، جایگذاری \deg r_{i+1}<\deg r_i. بجای 0\le r_{i+1}<|r_i| است. بقیه مشابه حالت قبل باقی میماند. تفاوت دوم در محدودیتی است که بر اندازهٔ ضرایب بزو که از تعمیم الگوریتم اقلیدس به دست میاید وجود دارد، که درمورد چند جمله ای دقیق تر است. اگر a و b دو چند جمله‌ی غیر صفر باشند الگوریتم تعمیم یافته (s,t) را به گونه ای به دست میاورد که در شرایط زیر صدق کند:

as+bt=\gcd(a,b)

و 

\deg s <\deg b - \deg (\gcd(a,b)), \quad \deg t <\deg a - \deg (\gcd(a,b)).

تفاوت سوم در این است که بزرگترین مقسوم علیه مشترک فقط بصورت ضرب یک ثابت غیر صفر تعریف میشود. راههای مختلفی برای تعریف بزرگترین مقسوم علیه مشترک به صورت غیر مبهم وجود دارد. در ریاضیات معمولاً به چند جمله ای که ب.م.م همهٔ ضریب‌هایش یک هست نیاز است. برای رسیدن به این مقصود کافیست هر خروجی را بر ضریب بزرگترین توان r_{k}.   تقسیم کنیم. اگر a و b نسبت به هم اول باشند در سمت راست نامساوی بزو یکی ۱ میشود، در غیر این صورت یکی ممکن است هر مقدار ثابت غیر صفر شود. در جبر کامپیوتر، چند جمله ای معمولاً ضرایب صحیح را می‌پذیرد، و این راه ساده سازی بزرگترین مقسوم علیه مشترک برای سهولت تعداد بسیار زیادی بخش ایجاد می‌کند. راه دوم ساده سازی بزرگترین مقسوم علیه مشترک در حالت چند جمله ای با ضرایب صحیح تقسیم بر بزرگترین عمل مشترک بین ضرایب r_{k}, برای رسیدن به چند جمله ای اصلی (یعنی چند جمله ای که بزرگترین عامل مشترک ضرایبش ۱ است). اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند این نرمال سازی بزرگترین مقسوم علیه مشترک را یک میدهد. اشکال این روش محاسبه، وجود زیر مساله‌های زیاد است که باید محاسبه و ساده شوند.  روش سوم شامل تعمیم الگوریتم subresultant pseudo-remainder sequences که مشابه تعمیم الگوریتم اقلیدسی به الگوریتم تعمیم یافته است. این روش این امکان را فراهم می‌کند که وقتی با چند جمله ای با ضرایب صحیح شروع می‌کنیم هر چند جمله ای که بدست میاید ضرایبش، صحیح باشد. علاوه بر این هر باقی‌مانده محاسبه شده یک چند جمله‌ای subresultant است. در حالت خاص اگر چند جمله‌ی‌های ورودی نسبت به هم اول باشند آنگاه طبق قضیه بزو میشود:

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

 که \operatorname{Res}(a,b) برابر resultant ، a,bاست. در این فرم قضیه بزو مقسوم علیه دیده نمی‌شود. اگر همه چیز را بر resultant تقسیم کنیم قضیه کلاسیک بزو بدست می آید ،با یک مقسوم علیه مشترک ساده برای اعداد گویایی که در آن ظاهر میشوند.

شبه‌کد[ویرایش]

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

برای مثال

(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 وجود داشته باشند که

ns+at=1

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

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 ساخته شده است،ممکن است توسط حلقه ی خارج قسمت های K[X]/\langle p\rangle, به طور یکتا شناسایی شود،و اعضایش در یک رابطه ی یک به یک و و پوشا با چندجمله ای هایی با درجات کمتر از 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

مثال[ویرایش]

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

step  quotient  r, newr t, newt
   p = x8 + x4 + x3 + x + 1   0
   a = x6 + x4 + x + 1  1
1  x2 + 1  x2 = p - a (x2 + 1)  x2 + 1 = 0 - 1 × (x2 + 1)
2  x4 + x2  x + 1 = a - x2 (x4 + x2)  x6 + x2 + 1 = 1 - (x4 + x2) (x2 + 1)
3  x + 1  1 = x2 - (x + 1) (x + 1)  x7 + x6 + x3 + x = (x2 + 1) - (x + 1) (x6 + x2 + 1)
4  x + 1  0 = (x + 1) - 1 × (x + 1)  

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

الگوریتم تعمیم یافته اقلیدس برای بیش از دو عدد[ویرایش]

ما میتوانیم در موردی که تعداد اعداد بیش از دو تا هست،به طور پشت سر هم(دو تا باهم و سپس حاصل آنها با عدد بعدی) از این الگوریتم استفاده کنیم.اول باید اثبات کنیم که \gcd(a,b,c) = \gcd(\gcd(a,b),c).برای این اثبات اگر d=\gcd(a,b,c)باشد،طبق تعریف میتوان گفت که d مقسوم علیه مشترک a و b هست.بنابراین برای یک مقدار خاص k داریم\gcd(a,b)=k d .مشابها d مقسوم علیه c هم هست،پس برای یک مقدار خاصی ازj c=jd.اگر u=\gcd(k,j) با این تعریف ما از u، ud | a,b,c اما چون d بزرگترین مقسوم علیه هستu وارون ضربی دارد.(unit هست.) بنابراین اگر na + mb = \gcd(a,b) پس مقادیر x و y وجود دارند به طوریکه x\gcd(a,b) + yc = \gcd(a,b,c). بنابراین معادله ی نهایی به شکل : x(na + mb) + yc = (xn)a + (xm)b + yc =  \gcd(a,b,c).\, خواهد بود. پس اگر ما آن را با استقرا روی n عدد انجام دهیم به معادله ی زیر میرسیم

\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),

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

منابع[ویرایش]

پیوند به بیرون[ویرایش]