خوارزمية إقليدية موسعة

في الحساب وبرمجة الحاسوب ، تُعد خوارزمية إقليدس الموسعة امتدادًا لخوارزمية إقليدس ، وهي تحسب، بالإضافة إلى القاسم المشترك الأكبر (gcd) للأعداد الصحيحة a و b ، معاملات متطابقة بيزو ، وهي أعداد صحيحة x و y بحيث${\displaystyle ax+by=\gcd(a,b)}$ويُشار إليه عمومًا بـ${\displaystyle \operatorname {xgcd} (a,b)}$.

هذه خوارزمية تحقق ، لأن القاسم المشترك الأكبر هو العدد الوحيد الذي يمكنه في آنٍ واحد تحقيق هذه المعادلة وقسمة المدخلات. ^{[ 1 ]} كما أنها تسمح بحساب ناتج قسمة a و b على قاسمهما المشترك الأكبر، بتكلفة إضافية شبه معدومة.

يشير مصطلح "الخوارزمية الإقليدية الموسعة" أيضًا إلى خوارزمية مشابهة جدًا لحساب القاسم المشترك الأكبر لكثير الحدود ومعاملات هوية بيزو لكثيري حدود أحاديي المتغير .

تُعدّ خوارزمية إقليدس الموسّعة مفيدةً للغاية عندما يكون a و b عددين أوليين فيما بينهما . في هذه الحالة، يكون x هو المعكوس الضربي المعياري لـ a بتردد b ، ويكون y هو المعكوس الضربي المعياري لـ b بتردد a . وبالمثل، تسمح خوارزمية إقليدس الموسّعة متعددة الحدود بحساب المعكوس الضربي في امتدادات الحقول الجبرية ، وخاصةً في الحقول المنتهية ذات الرتبة غير الأولية. ونتيجةً لذلك، تُستخدم كلتا خوارزميتي إقليدس الموسّعتين على نطاق واسع في علم التشفير . وعلى وجه الخصوص، يُعدّ حساب المعكوس الضربي المعياري خطوةً أساسيةً في اشتقاق أزواج المفاتيح في طريقة تشفير المفتاح العام RSA .

تعتمد خوارزمية إقليدس القياسية على سلسلة من عمليات القسمة الإقليدية التي لا تُستخدم نواتجها، بل يُحتفظ فقط بالبواقي . أما في الخوارزمية الموسعة، فتُستخدم نواتج القسمة المتتالية. وبشكل أدق، تتكون خوارزمية إقليدس القياسية، عند إدخال a و b ، من حساب سلسلة من العمليات.${\displaystyle q_{1},\ldots ,q_{k}}$من نواتج القسمة ومتتالية${\displaystyle r_{0},\ldots ,r_{k+1}}$من البواقي بحيث

${\displaystyle {\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\quad {\text{and}}\quad 0\leq r_{i+1}<|r_{i}|\quad {\text{(this defines }}q_{i})\\&\,\,\,\vdots \end{aligned}}}$

تتمثل الخاصية الرئيسية للقسمة الإقليدية في أن المتباينات على اليمين تحدد بشكل فريد${\displaystyle q_{i}}$و${\displaystyle r_{i+1}}$من${\displaystyle r_{i-1}}$و${\displaystyle r_{i}.}$

تتوقف العملية الحسابية عند الوصول إلى باقي القسمة${\displaystyle r_{k+1}}$وهو صفر؛ القاسم المشترك الأكبر هو آخر باقي غير صفري${\displaystyle r_{k}.}$

تتبع خوارزمية إقليدس الموسعة نهجًا مشابهًا، ولكنها تضيف سلسلتين أخريين، كما يلي

${\displaystyle {\begin{aligned}r_{0}&=a&r_{1}&=b\\s_{0}&=1&s_{1}&=0\\t_{0}&=0&t_{1}&=1\\&\,\,\,\vdots &&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}&{\text{and }}0&\leq r_{i+1}<|r_{i}|&{\text{(this defines }}q_{i}{\text{)}}\\s_{i+1}&=s_{i-1}-q_{i}s_{i}\\t_{i+1}&=t_{i-1}-q_{i}t_{i}\\&\,\,\,\vdots \end{aligned}}}$

تتوقف العملية الحسابية أيضًا عندما${\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 t_{k+1}=\mp {\frac {a}{\gcd(a,b)}}}$( اللافتة)${\displaystyle \mp }$عكس${\displaystyle \pm }$).

علاوة على ذلك، إذا كانت كل من a و b موجبة و${\displaystyle \gcd(a,b)\neq \min(a,b)}$، ثم

${\displaystyle |s_{i}|\leq \left\lfloor {\frac {b}{2\gcd(a,b)}}\right\rfloor \quad {\text{and}}\quad |t_{i}|\leq \left\lfloor {\frac {a}{2\gcd(a,b)}}\right\rfloor }$

ل${\displaystyle 0\leq i\leq k,}$أين${\displaystyle \lfloor x\rfloor }$يشير إلى الجزء الصحيح من x ، أي أكبر عدد صحيح لا يزيد عن x .

وهذا يعني أن زوج معاملات بيزو الذي توفره خوارزمية إقليدس الموسعة هو الزوج الأدنى من معاملات بيزو، باعتباره الزوج الوحيد الذي يحقق كلا المتباينتين أعلاه.

وهذا يعني أيضًا أنه إذا كان a و b مناسبين لنوع بيانات عدد صحيح غير موقع ، فيمكن لبرنامج الكمبيوتر حساب معاملات بيزو في نوع العدد الصحيح الموقع المقابل دون حدوث تجاوز في عدد صحيح .

أمثلة

يوضح الجدول التالي كيفية عمل خوارزمية إقليدس الموسعة مع المدخلين 240 و 46 . القاسم المشترك الأكبر هو آخر عنصر غير صفري، وهو 2 في عمود "الباقي". تتوقف العملية الحسابية عند الصف 6، لأن الباقي فيه يساوي صفرًا . تظهر معاملات بيزو في العمودين الأخيرين من الصف قبل الأخير. في الواقع، من السهل التحقق من أن −9 × 240 + 47 × 46 = 2. أخيرًا، العنصران الأخيران 23 و −120 من الصف الأخير هما، مع مراعاة الإشارة، ناتج قسمة المدخلين 46 و 240 على القاسم المشترك الأكبر 2 .

الفهرس i	خارج القسمة q i −1	الباقي ر ي	s i	تي آي
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

يستخدم المثال التالي رمزًا أكثر اختصارًا. القاسم المشترك الأكبر لـ${\displaystyle a=68}$و${\displaystyle b=30}$يمكن حسابها على النحو التالي:

${\displaystyle g=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;\;^{\uparrow }\!\!-\!-\!(-2)}{(68,30)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!(-3)\!-\!\!-\!^{\uparrow }\;\;}{(8,30)}}}$${\displaystyle =\mathrm {gcd} {\underset {\color {Green}\scriptstyle \;^{\uparrow }\!\!-\!\!-\!(-1)\!\!}{(8,\,6)}}=\mathrm {gcd} {\underset {\color {Green}\scriptstyle \!\!(-3)\!-\!\!-\!^{\uparrow }\;}{(2,\,6)}}=\mathrm {gcd} (2,0)=2,}$

أين${\displaystyle \color {Green}\scriptstyle \,^{\uparrow }\!\!-\!-\!(-2)}$الخطوة الأولى تعني أن${\displaystyle -2}$أوقات${\displaystyle 30}$يُضاف إلى${\displaystyle 68}$(لا يتغير القاسم المشترك الأكبر عند إضافة مضاعف لأحد الأرقام إلى الآخر).

بتطبيق عمليات الجمع المشار إليها باللون الأخضر للمضاعفات بشكل مماثل للمعادلات، بدءًا من${\displaystyle a=1a+0b}$و${\displaystyle b=0a+1b,}$يؤدي إلى${\displaystyle g=4a-9b,}$وفقًا للحسابات المجاورة (يستخدم الجدول المقابل في أقصى اليمين عمليات الصفوف).

بالنسبة لكثيرات الحدود أحادية المتغير ذات المعاملات في حقل ، تعمل جميع الطرق بشكل مشابه، من القسمة الإقليدية إلى متطابقة بيزو والخوارزمية الإقليدية الموسعة. يتمثل الاختلاف الأول في أن المتباينة في القسمة الإقليدية والخوارزمية${\displaystyle 0\leq r_{i+1}<|r_{i}|}$يجب استبدالها بمتباينة على الدرجات${\displaystyle \deg r_{i+1}<\deg r_{i}.}$بخلاف ذلك، يبقى كل ما سبق في هذه المقالة كما هو، ببساطة عن طريق استبدال الأعداد الصحيحة بكثيرات الحدود.

يتمثل الاختلاف الثاني في الحد الأقصى لحجم معاملات بيزو التي توفرها خوارزمية إقليدس الموسعة، والتي تكون أكثر دقة في حالة كثير الحدود، مما يؤدي إلى النظرية التالية.

إذا كان a و b كثيرتي حدود غير صفريتين، فإن خوارزمية إقليدس الموسعة تنتج زوجًا فريدًا من كثيرات الحدود ( s , t ) بحيث

${\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}.}$يسمح هذا بأنه إذا كان a و b عددين أوليين فيما بينهما، نحصل على 1 في الطرف الأيمن من متباينة بيزو. وإلا، فقد نحصل على أي ثابت غير صفري. في الجبر الحاسوبي ، عادةً ما تكون معاملات كثيرات الحدود أعدادًا صحيحة، وهذه الطريقة لتطبيع القاسم المشترك الأكبر تُدخل عددًا كبيرًا جدًا من الكسور مما يجعلها غير عملية.

الطريقة الثانية لتطبيع القاسم المشترك الأكبر في حالة كثيرات الحدود ذات المعاملات الصحيحة هي قسمة كل ناتج على محتوى${\displaystyle r_{k},}$للحصول على قاسم مشترك أكبر أولي . إذا كانت كثيرات الحدود المدخلة أولية فيما بينها، فإن هذا التوحيد يوفر أيضًا قاسمًا مشتركًا أكبر يساوي 1. لكن يعيب هذه الطريقة ضرورة حساب وتبسيط العديد من الكسور أثناء العملية الحسابية.

يتمثل النهج الثالث في توسيع خوارزمية متواليات الباقي الزائفة الناتجة بطريقة مشابهة لتوسيع خوارزمية إقليدس إلى خوارزمية إقليدس الموسعة. وهذا يسمح بأنه عند البدء بكثيرات حدود ذات معاملات صحيحة، فإن جميع كثيرات الحدود التي يتم حسابها لها معاملات صحيحة. علاوة على ذلك، فإن كل باقي محسوب${\displaystyle r_{i}}$هي متعددة حدود فرعية . على وجه الخصوص، إذا كانت متعددات الحدود المدخلة أولية فيما بينها، فإن متطابقة بيزو تصبح

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

أين${\displaystyle \operatorname {Res} (a,b)}$يرمز إلى محصلة a و b . في هذا الشكل من متطابقة بيزو، لا يوجد مقام في الصيغة. إذا قسمنا كل شيء على المحصلة، نحصل على متطابقة بيزو الكلاسيكية، مع وجود مقام مشترك صريح للأعداد النسبية التي تظهر فيها.

لتطبيق الخوارزمية الموضحة أعلاه، تجدر الإشارة أولاً إلى أنه لا يلزم سوى آخر قيمتين للمتغيرات المفهرسة في كل خطوة. وبالتالي، لتوفير الذاكرة، يجب استبدال كل متغير مفهرس بمتغيرين فقط.

لتبسيط الأمور، تستخدم الخوارزمية التالية (والخوارزميات الأخرى في هذه المقالة) عمليات إسناد متوازية . في لغة برمجة لا تدعم هذه الميزة، يجب محاكاة عمليات الإسناد المتوازية باستخدام متغير مساعد. على سبيل المثال، الخوارزمية الأولى،

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

يعادل

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

وينطبق الأمر نفسه على عمليات التعيين المتوازية الأخرى. وهذا يؤدي إلى الكود التالي:

دالة extended_gcd(a, b) (old_r, r) := (a, b) (old_s, s) := (1, 0) (old_t, t) := (0, 1) بينما r ≠ 0، قم بما يلي: ÷ r القديمة ÷ 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) إخراج "معاملات بيزو:", (old_s, old_t) إخراج "القاسم المشترك الأكبر:", old_r إخراج "ناتج القسمة على القاسم المشترك الأكبر:", (t, s)

قد يكون ناتج قسمة a و b على قاسمهما المشترك الأكبر، والذي يُخرَج في البرنامج، ذا إشارة خاطئة. من السهل تصحيح ذلك في نهاية العملية الحسابية، ولكن لم يتم ذلك هنا لتبسيط الكود. وبالمثل، إذا كان أحد a أو b يساوي صفرًا والآخر سالبًا، فسيكون القاسم المشترك الأكبر الناتج سالبًا، ويجب تغيير جميع إشارات الناتج.

وأخيرًا، لاحظ أنه في هوية بيزو،${\displaystyle ax+by=\gcd(a,b)}$يمكن للمرء أن يحلها${\displaystyle y}$منح${\displaystyle a,b,x,\gcd(a,b)}$وبالتالي، فإن تحسين الخوارزمية المذكورة أعلاه يتمثل في حساب فقط${\displaystyle s_{k}}$المتتالية (التي تُنتج معامل بيزو)${\displaystyle x}$ثم احسب${\displaystyle y}$في نهايةالمطاف:

دالة extended_gcd(a, b) s := 0; old_s := 1 r := b; old_r := a بينما r ≠ 0، قم بما يلي: ÷ r القديمة ÷ r (old_r, r) := (r, old_r − quotient × r) (old_s, s) := (s, old_s − quotient × s) إذا كان b ≠ 0، فإن bezout_t := (old_r − old_s × a) div b، وإلا bezout_t := 0 إخراج "معاملات بيزو:", (old_s, bezout_t) إخراج "القاسم المشترك الأكبر:", old_r

مع ذلك، في كثير من الحالات، لا يُعدّ هذا تحسينًا حقيقيًا: فبينما لا تتأثر الخوارزمية السابقة بتجاوز السعة عند استخدامها مع الأعداد الصحيحة للآلة (أي الأعداد الصحيحة ذات الحد الأعلى الثابت للأرقام)، فإن عملية ضرب old_s × a في حساب bezout_t قد تؤدي إلى تجاوز السعة، مما يحدّ من هذا التحسين للمدخلات التي يمكن تمثيلها بأقل من نصف الحجم الأقصى. عند استخدام أعداد صحيحة ذات حجم غير محدود، يزداد الوقت اللازم للضرب والقسمة تربيعيًا مع حجم الأعداد الصحيحة. هذا يعني أن "التحسين" يستبدل سلسلة من عمليات الضرب/القسمة لأعداد صحيحة صغيرة بعملية ضرب/قسمة واحدة، والتي تتطلب وقتًا حسابيًا أكبر من العمليات التي تستبدلها مجتمعة.

يكون الكسر a / b في صورته المبسطة القياسية إذا كان a و b عددين أوليين فيما بينهما وكان b موجبًا. ويمكن الحصول على هذه الصورة المبسطة القياسية باستبدال أسطر الإخراج الثلاثة للرمز الزائف السابق بـ

إذا كانت قيمة s تساوي صفرًا، فسيتم طباعة "القسمة على صفر" . إذا كانت قيمة s أقل من صفر، فسيتم تعيين قيمة s إلى -s وقيمة t إلى -t ( لتجنب المقامات السالبة ). إذا كانت قيمة s تساوي واحدًا، فسيتم طباعة -t ( لتجنب المقامات التي تساوي واحدًا). ​​سيتم طباعة -t / s .

يعتمد برهان هذه الخوارزمية على حقيقة أن s و t عددان صحيحان أوليان فيما بينهما بحيث يكون s + bt = 0 ، وبالتالي${\displaystyle {\frac {a}{b}}=-{\frac {t}{s}}}$للحصول على الشكل المبسط المتعارف عليه، يكفي تحريك علامة السالب للحصول على مقام موجب.

إذا كان b يقسم a بالتساوي، فإن الخوارزمية تُنفذ دورة واحدة فقط، ويكون s = 1 في نهاية الخوارزمية. هذه هي الحالة الوحيدة التي يكون فيها الناتج عددًا صحيحًا.

تُعدّ خوارزمية إقليدس الموسّعة الأداة الأساسية لحساب المعكوسات الضربية في البنى النمطية، وتحديدًا في الأعداد الصحيحة النمطية وامتدادات الحقول الجبرية . ومن الأمثلة البارزة على الحالة الأخيرة الحقول المنتهية ذات الرتبة غير الأولية.

دالة معكوسة (أ، ن) t := 0; newt := 1 r := n; newr := a بينما newr ≠ 0 حاصل القسمة := r div newr (t, newt) := (newt, t − ÷ient × newt) (ص، نيور) := (نيور، ص - حاصل الضرب × نيور) إذا كانت قيمة r أكبر من 1، فأرجع "المصفوفة a غير قابلة للعكس". إذا كانت قيمة t أقل من 0، t := t + n أعد t

دالة معكوسة (أ، ص) t := 0; newt := 1 r := p; newr := a بينما newr ≠ 0 حاصل القسمة := r div newr (ص، نيور) := (نيور، ص - حاصل الضرب × نيور) (t, newt) := (newt, t − ÷ient × newt) إذا كانت درجة (r) > 0 ، فأرجع " إما أن p غير قابل للاختزال أو أن a من مضاعفات p".إرجاع (1/r) × t

يمكن معالجة حالة وجود أكثر من عددين بشكل تكراري. أولاً، سنوضح أن${\displaystyle \gcd(a,b,c)=\gcd(\gcd(a,b),c)}$لإثبات ذلك، لنفترض${\displaystyle d=\gcd(a,b,c)}$بحسب تعريف القاسم المشترك الأكبر${\displaystyle d}$هو قاسم لـ${\displaystyle a}$و${\displaystyle b}$. هكذا${\displaystyle \gcd(a,b)=kd}$بالنسبة للبعض${\displaystyle k}$. بصورة مماثلة${\displaystyle d}$هو قاسم لـ${\displaystyle c}$لذا${\displaystyle c=jd}$بالنسبة للبعض${\displaystyle j}$. يترك${\displaystyle u=\gcd(k,j)}$من خلال بنائه لـ${\displaystyle u}$،${\displaystyle ud|a,b,c}$لكن منذ ذلك الحين${\displaystyle d}$هو القاسم الأكبر${\displaystyle u}$هي وحدة . وبما أن${\displaystyle ud=\gcd(\gcd(a,b),c)}$لقد ثبتت النتيجة.

لذلك إذا${\displaystyle na+mb=\gcd(a,b)}$ ثم هناك${\displaystyle x}$و${\displaystyle y}$بحيث${\displaystyle x\gcd(a,b)+yc=\gcd(a,b,c)}$إذن ستكون المعادلة النهائية هي

${\displaystyle x(na+mb)+yc=(xn)a+(xm)b+yc=\gcd(a,b,c).\,}$

ثم نستخدم الاستقراء لتطبيقه على الأعداد n

${\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 ),}$

مع المعادلات التي تليها مباشرة.

• المجال الإقليدي
• نظرية التطابق الخطي
• كوتاكا

• كنوت، دونالد . فن برمجة الحاسوب . أديسون-ويسلي.المجلد الثاني، الفصل الرابع.
• توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 2001. ISBN 0-262-03293-7الصفحات 859 – 861 من القسم 31.2: القاسم المشترك الأكبر.

• مصدر شكل الخوارزمية المستخدمة لتحديد المعكوس الضربي في GF(2^8)