خوارزمية إقليدس الموسّعة: شرح مبسّط بالأمثلة والكود

خوارزمية إقليدس الموسّعة (Extended Euclidean Algorithm) هي نسخة مطوّرة من خوارزمية إقليدس، لا تكتفي بإيجاد القاسم المشترك الأكبر (GCD) لعددين صحيحين، بل تُعيد معه معاملين صحيحين x وy يحقّقان المعادلة:

a·x + b·y = gcd(a, b)

هذه المعادلة تُسمّى متطابقة بيزو (Bézout's identity)، وهي بالضبط ما يجعل الخوارزمية الموسّعة أداة لا غنى عنها في التشفير ونظرية الأعداد. فبدلاً من أن تعرف فقط "أن القاسم المشترك الأكبر لـ 30 و20 هو 10"، تعرف أيضاً كيف تُركّب الرقم 10 خطياً من العددين. وهذا ما يفتح الباب لحساب المعكوس الضربي وحلّ المعادلات، كما سنرى.

الفرق بين الخوارزمية العادية والموسّعة

خوارزمية إقليدس الكلاسيكية تعتمد على مبدأ بسيط: gcd(a, b) = gcd(b, a mod b)، وتُكرّر القسمة حتى يصبح الباقي صفراً. الموسّعة تُضيف تتبّعاً للمعاملات في كل خطوة رجوع.

المعيار	إقليدس العادية	إقليدس الموسّعة
الناتج	GCD فقط	GCD مع المعاملين x و y
متطابقة بيزو	لا تحسبها	تحسبها
المعكوس الضربي النمطي	لا	نعم
التعقيد الزمني	O(log min(a,b))	O(log min(a,b))
الاستخدام الأبرز	تبسيط الكسور، القواسم	RSA، فكّ التشفير، المعادلات

لاحظ أن التعقيد الزمني واحد في الحالتين؛ الإضافة "مجانية" تقريباً من حيث الأداء، وهذا سبب إضافي لتفضيل الموسّعة عندما تحتاج المعاملات.

كيف تعمل خطوة بخطوة

الطريقة الأوضح للفهم هي الطريقة التكرارية (recursive):

1. حالة التوقّف: إذا كان b = 0، فإن gcd(a, 0) = a، والمعاملان هما x = 1 وy = 0 لأن a·1 + 0·0 = a.
2. النداء الأعمق: احسب الخوارزمية على (b, a mod b) واحصل منها على gcd ومعاملين مؤقتين x1 وy1.
3. تحديث المعاملات عند الرجوع: المعاملان للمستوى الحالي هما:
   • x = y1
   • y = x1 − (a ÷ b) · y1 (حيث ÷ قسمة صحيحة).
4. كرّر الرجوع حتى تصل إلى المستوى الأعلى، فتحصل على x وy النهائيين.

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

مثال محلول بالكامل

لنحسب معاملات بيزو للعددين 240 و46.

خطوات القسمة (إقليدس العادية):

• 240 = 5 × 46 + 10
• 46 = 4 × 10 + 6
• 10 = 1 × 6 + 4
• 6 = 1 × 4 + 2
• 4 = 2 × 2 + 0 ← الباقي صفر، إذن gcd = 2

الآن نرجع خلف الخطوات لنكتب 2 كمزيج خطي:

• 2 = 6 − 1×4
• نعوّض 4 = 10 − 1×6 → 2 = 6 − 1×(10 − 6) = 2×6 − 10
• نعوّض 6 = 46 − 4×10 → 2 = 2×(46 − 4×10) − 10 = 2×46 − 9×10
• نعوّض 10 = 240 − 5×46 → 2 = 2×46 − 9×(240 − 5×46) = 47×46 − 9×240

النتيجة: 240×(−9) + 46×(47) = 2. تحقّق سريع: −2160 + 2162 = 2 ✓. فيكون x = −9 وy = 47.

المعكوس الضربي النمطي: التطبيق الأهم

هنا تلمع الخوارزمية فعلاً. لإيجاد المعكوس الضربي للعدد a بالنسبة للمقياس m (أي رقم a⁻¹ بحيث a·a⁻¹ ≡ 1 (mod m))، طبّق الخوارزمية الموسّعة على a وm. المعكوس موجود فقط إذا كان gcd(a, m) = 1.

مثال: أوجد معكوس 3 بالنسبة للمقياس 7.

• 7 = 2×3 + 1 → 1 = 7 − 2×3
• إذن −2×3 ≡ 1 (mod 7)، والمعكوس هو −2 mod 7 = 5.
• تحقّق: 3×5 = 15 = 14 + 1 ≡ 1 (mod 7) ✓

هذه الخطوة بالذات هي جوهر توليد المفتاح الخاص في RSA: يُحسب الأس الخاص d بوصفه معكوس الأس العام e بالنسبة لـ φ(n).

نموذج كود مختصر

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0            # gcd, x, y
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

# مثال
g, x, y = ext_gcd(240, 46)
print(g, x, y)   # 2 -9 47

يمكن كتابتها تكرارياً (iterative) بحلقة while لتفادي عمق النداءات، لكن النسخة أعلاه هي الأوضح للفهم.

خطأ شائع يجب تجنّبه

أكثر خطأ متكرّر هو الخلط في ترتيب تحديث المعاملات عند الرجوع، فيتبادل البعض x وy أو يُهمل الطرح x1 − (a÷b)·y1. القاعدة الآمنة: المعامل الجديد x يأخذ دائماً قيمة y من المستوى الأعمق، ثم y الجديد يُحسب من المعادلة. ونقطة أخرى: معاملات بيزو ليست وحيدة؛ فـ (x + k·b/g, y − k·a/g) تحلّ المعادلة لأي عدد صحيح k، لذلك قد تختلف نتيجتك عن نتيجة أداة أخرى وتبقى كلاهما صحيحة.

الأسئلة الشائعة

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

متى لا يوجد معكوس ضربي نمطي؟ عندما لا يكون gcd(a, m) = 1، أي عندما يشترك العددان في قاسم أكبر من واحد. عندها لا يوجد حل للمعادلة a·x ≡ 1 (mod m).

ما الفرق بينها وبين نظرية أويلر لحساب المعكوس؟ نظرية أويلر تحسب المعكوس بالأس a^(φ(m)−1) mod m، لكنها تتطلب معرفة φ(m) وتُكلّف حسابياً أكثر. خوارزمية إقليدس الموسّعة أسرع وأعمّ لأنها لا تحتاج تحليل m إلى عوامل.

هل هي جزء من "هياكل البيانات" فعلاً؟ هي خوارزمية عددية بحتة، لكنها تُدرّس ضمن مقررات "الخوارزميات وهياكل البيانات" لأنها أساس لمسائل التشفير والحوسبة النمطية التي تظهر كثيراً في مسابقات البرمجة والمقابلات التقنية.