خوارزمية أقليدس
خوارزمية إقليدس في نظرية الأعداد هي خوارزمية لحساب القاسم المشترك الأكبر لعددين طبيعيين، تظهر أهميتها الأساسية في عدم حاجتنا لتحليل الرقمين كي نتمكن من حساب القاسم المشترك الأكبر لهما، وتتميز بكونها إحدى أقدم الخوارزميات حيث ترجع إلى سنة 300 ق.م.
وصف الخوارزمية
القاسم المشترك الأكبر لعددين طبيعيين A، B يساوي القاسم المشترك الأكبر للعدد الثاني B وباقي قسمة A على B، ونكرر العملية نفسها حتى يصبح باقي القسمة مساويا الصفر، عندئذ يكون القاسم المشترك الأكبر هو العدد الآخر.
حيث :
r باقي قسمة A على B
N هو القاسم المشترك الأكبر.
مثال
القاسم المشترك الأكبر للعددين 252 و 198 :
252 = 198 * 1 + 54 ‘ أربع وخمسون هو باقي قسمة 252 على 198
فنجد القاسم المشترك للعددين 198 و 54
198 = 54 * 3 + 36 ‘ ست وثلاثون هو باقي القسمة.
نكرر العملية هذه المرة مع : 54 و 36
54 = 36 * 1 + 18
مرة أخرى : 36 = 18 * 2 + 0
هنا وصلنا للصفر فيكون العدد الثاني 18 هو القاسم المشترك الأكبر.
Extended Euclidean Algorithm الخوارزمية الإقليديه الممتدة
یمكن تمثیل القاسم المشترك الأعظم للعددین عن طریق دمج خطي مع عددین آخرین ، وذلك كالتالي GCD(x,y) = m*x + n*y كیف یمكن أیجاد قیمتي n و m وذلك عن طریق خوارزمیة اقلیدس الممتدة وھناك ثلاثة طرق لمعرفة ھذه القیم (الطرق ھي مشابھ لبعض ، لكن یمكن القول أنھا مختصره من الأخریات). القیم (الطرق ھي مشابھ لبعض ، لكن یمكن القول أنھا مختصره من الأخریات). الطريقة الأولى: وهي يمكن ان نطلق عليها التراجع وفي هذه الطريقة نقوم بالحل عن طريق خوارزمية اقليدس وبعدها تقول بالتراجع الخلفي لايجاد قيمتي m,n كما في المثال التالي: مثال: قم بتمثيل العددين 26و21 بطريقة اقليدس الممتده : فنبدأ بالحل كما هو الحال في طريقة اقليدس : 26 == 1* 21 + 5 و 21 = 4 * 5 + 1 و 5 == 5 * 1 + 0 وتتوقف عند الصفر. الآن المعادلة التي قبل المعادلة التي باقيها صفر أي المعادلة الثانية نقوم بكتابتها بالشكل التالي : 1 = 21 – 4 * 5 ………… [1] أیضا المعادلة الأولى بنفس الشكل : 5 = 26 – 1 * 21 …………[2]
الآن نعوض المعادلة [2] في [1] 1 = 21 – 4 * (26 – 1 * 21)
ومن غیر أجراء عملیة حسابیة ، فقط نفك القوس لینتج : 1 = 21 -4*26 +4*21 1=21(1+4)-4*26 حيث 21 عامل مشترك لیكون لدینا الناتج النھائي : 4*21 +21
1 = 5*21 + (-4)*26 نتاكد من النتيجة 5*21+ -4*26 والناتج يساوي واحد إذاً المعادلة صحيحة
اذاً قيمة m هي 5 وقيمة nهي -4
مصادر
- من كتاب مقدمة في التشفير بالطرق الكلاسيكية
| ملف:Nuvola apps edu mathematics-ar.svg | هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها. |
| ملف:Nuvola apps edu mathematics-ar.svg | بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات. |
bg:Алгоритъм на Евклид bn:ইউক্লিডীয় এলগরিদম ca:Algorisme d'Euclides cs:Eukleidův algoritmus de:Euklidischer Algorithmus el:Αλγόριθμος του Ευκλείδη Euclidean algorithm]] eo:Eŭklida algoritmo es:Algoritmo de Euclides fa:الگوریتم اقلیدس fi:Eukleideen algoritmi fr:Algorithme d'Euclide hu:Euklideszi algoritmus id:Algoritma Euklidean it:Algoritmo di Euclide ja:ユークリッドの互除法 ko:유클리드 호제법 lt:Euklido algoritmas lv:Eiklīda algoritms ml:യൂക്ലിഡിന്റെ അൽഗൊരിതം mn:Евклидийн алгоритм nds:Euklidsch Algorithmus nl:Algoritme van Euclides nn:Euklidsk algoritme no:Euklids algoritme pl:Algorytm Euklidesa pms:Algoritm d'Euclid pt:Algoritmo de Euclides ro:Algoritmul lui Euclid ru:Алгоритм Евклида simple:Euclidean algorithm sk:Euklidov algoritmus sl:Evklidov algoritem sr:Еуклидов алгоритам sv:Euklides algoritm tr:Öklid algoritması uk:Алгоритм Евкліда vi:Giải thuật Euclid zh:輾轉相除法
