مبدأ الخوارزمية:
خوارزمية إقليدس الموسعة (Extended Euclidean Algorithm) لا تحسب فقط القاسم المشترك الأكبر gcd(a, m) لعددين صحيحين a و m، بل تجد أيضاً عددين صحيحين x و y بحيث ax + my = gcd(a, m)。
هذا تطبيق لمعادلة بيزو (Bézout's identity).
خطوات الخوارزمية:
- خوارزمية إقليدس:استخدام القسمة المتكررة لحساب gcd(a, m) مع تسجيل ناتج القسمة والباقي في كل خطوة
- التعويض الخلفي:البدء من الخطوة الأخيرة والتعويض عكسياً لتمثيل كل باقٍ كتركيبة خطية من a و m
- إيجاد المعاملات:الحصول أخيراً على المعاملين x و y بحيث ax + my = gcd(a, m)
المعكوس الضربي (Modular Inverse):
عندما يكون gcd(a, m) = 1 (أي أن a و m أوليان نسبياً)، يوجد معكوس ضربي لـ a بترديد m، يُرمز له بـ a-1 mod m. في هذه الحالة x هو المعكوس الضربي، بحيث a × x ≡ 1 (mod m)。
إذا كان x سالباً، يجب تعديله إلى موجب: x' = x mod m.
حالات الاستخدام:
- التشفير:حساب المفتاح الخاص في خوارزمية RSA يتطلب إيجاد المعكوس الضربي
- مسائل نظرية الأعداد:حل معادلات التطابق الخطي ax ≡ b (mod m)
- الرياضيات التوافقية:حساب المعاملات في الحسابات المعيارية (نظرية لوكاس، إلخ)
- البرمجة التنافسية:حساب سريع للمعكوس الضربي في الحسابات المعيارية
التعقيد الزمني:
O(log min(a, m))، مماثل لخوارزمية إقليدس
معادلة بيزو (Bézout's Identity):
لأي عددين صحيحين a و m، يوجد عددان صحيحان x و y بحيث ax + my = gcd(a, m). يمكن حساب هذين المعاملين x و y بكفاءة باستخدام خوارزمية إقليدس الموسعة.