اختبارات بساطة فيرما وميلر رابين

تحية للمواطنين هابروفسك! نواصل اليوم تبادل المواد المفيدة ، والتي تم إعداد ترجمة لها خصيصًا لطلاب الدورة "خوارزميات للمطورين" .



بالنظر إلى عدد n ، كيف نفهم أن هذا الرقم أولي؟ افترض أن n غريب في البداية ، لأن المهمة بسيطة للغاية.

ستكون الفكرة الأكثر وضوحًا هي البحث عن جميع المقسومات على n ، ومع ذلك ، فإن المشكلة الرئيسية حتى الآن هي إيجاد خوارزمية فعالة.

---

اختبار المزرعة

وفقًا لنظرية فيرما ، إذا كانت n أولية ، فبالنسبة لأيٍّ من الحقوق التالية: المساواة a n−1 =1 (mod n) . من هنا يمكننا استنباط قاعدة اختبار Fermat للتحقق من بساطة الرقم: خذ عشوائيًا a ∈ {1, ..., n−1} وتحقق ما إذا كانت المساواة بين a n−1 =1 (mod n) . إذا لم يتم احترام المساواة ، فمن المرجح أن n مركب.

ومع ذلك ، يمكن تحقيق شرط المساواة حتى لو كانت n ليست بسيطة. على سبيل المثال ، خذ n = 561 = 3 × 11 × 17 . حسب النظرية الباقية الصينية:

Z 561 = Z 3 × Z 11 × Z 17

، حيث تقابل كل a Z ^∗ ₅₆₁ ما يلي:

(x,y,z) ∈ Z ∗ 3 ×Z ∗ 11 11×Z ∗ 17 .

حسب نظرية فيرما ، x 2 =1 ، y 10 =1 ، z 16 =1 . بما أن 2 و 10 و 16 جميعها 560 مقسمة ، فهذا يعني أن (x,y,z) 560 = (1, 1, 1) ، وبعبارة أخرى a 560 = 1 لأي a ∈ Z ∗ 561 .

لا يهم أيًا من الخيارات التي نختارها ، 561 سيجتاز دائمًا اختبار Fermat على الرغم من حقيقة أنه مركب ، طالما أنه يمثل coprime مع n . تسمى هذه الأرقام بأرقام كارمايكل ويتضح أن هناك عددًا لا حصر له منها.

إذا لم يكن a coprime مع n ، فهو لا يجتاز اختبار Fermat ، لكن في هذه الحالة يمكننا رفض الاختبارات ومواصلة البحث عن المقسومات على n ، بحساب GCD ( a ، n ).

اختبار ميلر رابين

يمكننا تحسين الاختبار بالقول إن n أولي إذا وفقط إذا كانت الحلول x 2 = 1 (mod n) هي x = ±1 .

وبالتالي ، إذا نجحت n في اختبار Fermat ، a n−1 = 1 ، فإننا نتحقق أيضًا من أن a (n−1)/2 = ±1 ، لأن ^{a (n−1)/2} هي الجذر التربيعي لـ 1.

لسوء الحظ ، فإن الأرقام مثل ، على سبيل المثال ، 1729 - رقم كارمايكل الثالث لا يزال بإمكانه خداع هذا الاختبار المحسن. ماذا لو كنا تكرار؟ هذا يعني أنه بينما سيكون ذلك ممكنًا ، فسوف نقوم بتقليل الأس بمقدار النصف ، حتى نصل إلى رقم غير الرقم 1. إذا وصلنا في النهاية إلى شيء بخلاف -1 ، فسيكون n مركبًا.

بشكل أكثر رسمية ، دع 2 ^S أكبر قوة لـ 2 ، قابلة للقسمة على n-1 ، أي ، n−1=2 S q لبعض الأرقام الفردية q . كل رقم من التسلسل

a n−1 = a (2^S)q ، a (2^S-1)q ، ...، aq .

هذا هو الجذر التربيعي للعضو السابق في التسلسل.

إذا كان n هو رقم أولي ، فيجب أن يبدأ التسلسل بالرقم 1 ويجب أن يكون كل رقم لاحق أيضًا 1 ، أو قد لا يكون العضو الأول في التسلسل واحدًا ، ولكن بعد ذلك يكون -1.

اختبار ميلر رابين يأخذ a∈ Z n عشوائي. إذا لم يبدأ التسلسل أعلاه بالرقم 1 ، أو إذا كان العضو الأول في التسلسل ليس 1 أو -1 ، فإن n ليست بسيطة.

اتضح أنه بالنسبة لأي n مركب ، بما في ذلك أرقام Carmichael ، فإن احتمال اجتياز اختبار Miller-Rabin هو 1/4 تقريبًا. (في المتوسط ​​، أقل من ذلك بكثير). وبالتالي ، فإن احتمال اجتياز اختبار n عدة مرات يتناقص بشكل كبير.

إذا لم ينجح n في اختبار Miller-Rabin بتسلسل يبدأ بـ 1 ، عندئذٍ لدينا الجذر التربيعي غير التافه لـ 1 modulo n ، ويمكننا إيجاد مقسومات n بكفاءة . لذلك ، أرقام Carmichael هي دائما مريحة لعامل.

عندما يتم تطبيق الاختبار على أرقام النموذج pq ، حيث p و q يمثلان عددًا كبيرًا من الأعداد الأولية ، فإنهم لا يجتازون اختبار Miller-Rabin في جميع الحالات تقريبًا ، لأن التسلسل لا يبدأ بـ 1. لذلك ، لن نتمكن من كسر RSA.

في الممارسة العملية ، يتم تطبيق اختبار ميلر رابين على النحو التالي:

1. بالنظر إلى n ، نحتاج إلى إيجاد s بحيث تكون n – 1 = 2 S q لبعض الشيء q .
2. خذ عشوائي a ∈ {1,...,n−1}
3. إذا كانت ^q = 1 ، فإن n يجتاز الاختبار ونتوقف عن التنفيذ.
4. بالنسبة إلى i= 0, ... , s−1 تحقق من المساواة a (2^i)q = −1 . إذا ثبتت المساواة ، عندئذٍ يجتاز n الاختبار (إيقاف التنفيذ).
5. إذا لم يتم استيفاء أي من الشروط المذكورة أعلاه ، فإن n مركب.

قبل إجراء اختبار Miller-Rabin ، يجدر بنا إجراء عدد قليل من الانقسامات التافهة في أعداد صغيرة.

بالمعنى الدقيق للكلمة ، هذه الاختبارات عبارة عن اختبارات لمعرفة ما إذا كان الرقم مركبًا ، حيث إنه لا يثبت في الحقيقة أن الرقم الذي يتم فحصه أولي ، ولكنه يثبت بالتأكيد أنه يمكن أن يتحول إلى مركب.

لا تزال هناك خوارزميات حتمية تعمل في كثير من الأحيان لتحديد البساطة (Agrawal ، Kayal و Saxena ) ، لكنها اليوم تعتبر غير عملية.