نظرية الأعداد والحساب المودولي: مسائل تدريبية مع حلول خطوة بخطوة

1البواقي والتطابقات

قسمة a على n تعطي خارج قسمة q وباقيًا r: a = q·n + r مع 0 ≤ r < n. يُكتب الباقي a mod n. وفي حالة عدد سالب يكون q سالبًا أيضًا: −3 = −1·7 + 4، إذن −3 mod 7 = 4.

يكون عددان متطابقين بالنسبة إلى n، a ≡ b (mod n)، عندما يتركان الباقي نفسه، أي عندما يقسم n الفرق a − b.

يمكن اختزال البواقي في كل خطوة، مما يُبقي الأعداد صغيرة:

مثلًا 47·58 mod 9: 47 ≡ 2 و 58 ≡ 4، إذن 47·58 ≡ 8 (mod 9).

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

القاسم المشترك الأكبر gcd(a, b) هو أكبر عدد يقسم العددين. تستخدم خوارزمية إقليدس العلاقة gcd(a, b) = gcd(b, a mod b):

1. اقسم: a = q·b + r.
2. استبدل (a, b) بـ (b, r).
3. كرّر حتى يصبح الباقي 0. آخر باقٍ غير صفري هو القاسم المشترك الأكبر.

ومنه يُستنتج المضاعف المشترك الأصغر: lcm(a, b) = a·b / gcd(a, b).

3المعكوسات والخوارزمية الموسّعة

معكوس a بالنسبة إلى n هو العدد x الذي يحقق a·x ≡ 1 (mod n). يوجد بالضبط عندما gcd(a, n) = 1.

تنفّذ خوارزمية إقليدس الموسّعة إقليدس على (n, a) وتحتفظ بمعامل t لكل باقٍ، بحيث يكون كل باقٍ r ≡ t·a (mod n). ابدأ بـ t = 0 لـ n و t = 1 لـ a؛ كل t جديد هو t الصف قبل السابق ناقص q ضرب t الصف السابق. عندما يظهر الباقي 1 يكون t الخاص به هو المعكوس.

مع المعكوس يُحَلّ التطابق a·x ≡ b (mod n) بـ x ≡ a⁻¹·b. وعندما يكون d = gcd(a, n) أكبر من 1 يوجد d حلًّا إذا كان d يقسم b، ولا يوجد حل في غير ذلك.

لتطابقين بمقياسين أوليين فيما بينهما، x ≡ r₁ (mod m₁) و x ≡ r₂ (mod m₂)، حل واحد بالضبط بالنسبة إلى m₁·m₂ (مبرهنة الباقي الصينية). اكتب x = r₁ + m₁k وحلّ لإيجاد k.

4القوى المودولية وRSA

يحسب التربيع المتكرر aᵏ mod n بسرعة: اكتب k بالنظام الثنائي، وجد a و a² و a⁴ و a⁸ … mod n بالتربيع والاختزال، واضرب القوى التي بتّها 1.

مبرهنة فيرما الصغرى: لعدد أولي p لا يقسم a، aᵖ⁻¹ ≡ 1 (mod p). إذن يمكن اختزال الأس بالنسبة إلى p − 1.

يبني RSA مفتاحًا من عددين أوليين p و q:

1. n = p·q و φ(n) = (p − 1)(q − 1).
2. اختر e بحيث gcd(e, φ(n)) = 1؛ و(n, e) هو المفتاح العام.
3. احسب d = e⁻¹ mod φ(n): المفتاح الخاص.
4. التشفير c = mᵉ mod n؛ وفك التشفير m = cᵈ mod n.

تعدّ φ(n) لأويلر الأعداد من 1 إلى n التي أولية مع n: φ(p) = p − 1 لعدد أولي، φ(pᵏ) = pᵏ − pᵏ⁻¹، و φ ضربية لعوامل أولية فيما بينها.

5أخطاء شائعة

• إعطاء باقٍ سالب لعدد سالب: −17 mod 5 يساوي 3 لا −2.
• إيقاف إقليدس عند أول باقٍ بدل آخر باقٍ غير صفري.
• نسيان إضافة n إلى معامل سالب من الخوارزمية الموسّعة.
• حساب أس RSA d بالنسبة إلى n بدل φ(n).
• اختزال أس بالنسبة إلى p بدل p − 1 في مبرهنة فيرما.

6كيف تبدو أسئلة الامتحان

• سهل: القاسم المشترك الأكبر والبواقي. تنفّذ خوارزمية إقليدس لإيجاد gcd أو lcm، وتجد بواقي الأعداد السالبة، وتختزل المجاميع والجداءات بالنسبة إلى n.
• متوسط: المعكوسات والتطابقات. تجد المعكوسات المودولية بالخوارزمية الموسّعة، وتحل التطابقات الخطية، وتدمج تطابقين بمبرهنة الباقي الصينية، وتحسب φ(n) لأويلر.
• صعب: القوى المودولية وRSA. تستخدم التربيع المتكرر ومبرهنة فيرما، وتحل تطابقات ذات حلول عدة، وتجد الأسس الخاصة في RSA والنصوص المشفّرة والرسائل المفكوكة التشفير.