اختبار ميلر ورابين لأولية عدد ما

اختبار ميلر ورابين لأولية عدد ما (بالإنجليزية: Miller–Rabin primality test)‏ هو اختبار احتمالي لمعرفة إذا ما كان العدد أوليّاً: وهو خوارزمية تحدد فيما إذا كان العدد المعطى من المحتمل أن يكون أوليًا ، على غرار اختبار فيرمات لأولية عدد ما واختبار سولوفاي-ستراسن لأولية عدد ما.

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

المفهوم الرياضي

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

الأعداد الأولية القوية المحتملة

بنية الخوارزمية هي: بالنسبة إلى عدد صحيح فردي معين n > 2 ، لنكتب n في صورة 2^s⋅d + 1 حيث s و d عددان صحيحان موجبان و d عدد فردي. لنفكر في عدد صحيح a، يسمى القاعدة، يحقق 0 < a > n . بعد ذلك، يعتبر العدد n عدداً أولياً محتملاً للقاعدة a إذا كانت إحدى علاقات التطابق هذه صحيحة:

• $a^d\equiv 1(\mathrm{mod}n)$ ؛
• $a^{2^r\cdot d}\equiv -1(\mathrm{mod}n)$ 0≤ r <s .

الفكرة الكامنة وراء هذا الاختبار هي أنه عندما يكون n عددًا أوليًا فردياً، فإنه يجتاز الاختبار لوجود حقيقتين:

• من خلال مبرهنة فيرما الصغرى، $a^{n-1}\equiv 1(\mathrm{mod}n)$ (تحدد هذه الخاصية وحدها المفهوم الأضعف للقيمة الأولية المحتملة للقاعدة a ، والتي يعتمد عليها اختبار فيرما).
• باقي الجذور التربيعية الوحيدة لـ1 مع باقي القسمة للعدد n هي 1 و -1.

ومن ثم ، عن طريق عكس النقض ، إذا لم يكن n عددًا أوليًا محتملاً قويًا للقاعدة a ، فإن n بالتأكيد مركب ، ويسمى a شاهدًا على تركيب n (يُسمى أحيانًا بشكل خاطئ شاهد قوي ). ومع ذلك ، فإن هذه الخاصية ليست توصيفًا دقيقًا للأعداد الأولية. إذا كان n مركبًا ، فقد يكون مع ذلك أساسًا محتملاً قويًا للقاعدة a ، وفي هذه الحالة يطلق عليه اسم عدد شبه أولي قوي، و a هو قاعدة التشابه القوي.

اختيار القواعد

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

من أجل اختبار عشوائي كبير لرقم n، يعتبر اختبار القواعد عشوائياً خطوة أساسية، لأننا لا عرف انتشار الشهود والأعداد غير الحقيقة بين الأرقام 1 ، 2 ، ... ، n−1 . مع ذلك ، فإن مجموعة محددة مسبقًا من بعض القواعد الصغيرة تضمن تحديد جميع المركبات حتى حد أقصى محسوب مسبقًا. هذا الحد الأقصى بشكل عام كبير جدًا مقارنة بالقواعد. يعطي هذا اختبارات حتمية سريعة جدًا لـ n الصغيرة بما يكفي (انظر قسم الاختبار مقابل مجموعات صغيرة من القواعد أدناه ).