إقليدس الموسع – معاملات بيزو

يشغّل الخوارزم الموسع قسمات إقليدس ثم يسترجع بالتعويض الرجوعي لتعبير القاسم الأكبر بالمدخلين. للعددين 240 و46: 240 = 5×46 + 10 و46 = 4×10 + 6 و10 = 1×6 + 4 و6 = 1×4 + 2 و4 = 2×2 + 0 — فالقاسم 2. والاسترجاع يبنيه: 2 = 6 − 4 = 2×6 − 10 = 2×46 − 9×10 = 47×46 − 9×240. والتحقق: −2160 + 2162 = 2 ✓ فمعاملا بيزو (−9, 47). وتطبع الحاسبة جدول القسمات وسلسلة الاسترجاع كاملة وتحقق المتطابقة عددياً، وتربط الآلة بالمعكوسات المعيارية: اختزال s·a + t·b = g مقام b يظهر t ≡ a⁻¹ (mod b) كلما كان g = 1 — الخطوة التي تبني مفاتيح RSA الخاصة. وتُذكر الطرائق البديلة بالبقايا الموقعة والجدول التكراري.

1. 1

   أدخل a وb

   أي عددين صحيحين مثل 240 و46

2. 2

   شغّل القسمات

   يُطبع سلّم الخارج/الباقي

3. 3

   استرجع بالتعويض

   كل خطوة استرجاع تعيد بناء مزيج القاسم

4. 4

   تحقق من بيزو

   يفحص −9×240 + 47×46 = 2 عددياً

• 1

  بيزو موجودة دائماً: gcd(a,b) = sa + tb لصحيحين ما

• 2

  عندما gcd = 1 فمعامل a هو معكوسه مقام b

• 3

  الاسترجاع ميكانيكي — اكتب كل تبديل باقٍ

• التوقف عند القاسم دون الاسترجاع

• أخطاء إشارة عند تعويض البواقي صعوداً

• نسيان التحقق من أن sa + tb يعيد القاسم

• سوء قراءة أي المعاملين يعكس أي المدخلين