مبدأ الخوارزمية:
Miller-Rabin هي خوارزمية اختبار أولية احتمالية، تعتمد على تعميم نظرية فيرما الصغرى. للعدد الفردي n، اكتب n-1 بالصيغة 2^r × d، ثم اختبر ما إذا كان يحقق:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
جولات الاختبار والدقة:
- الاختبار الاحتمالي:اختيار قواعد عشوائية a، كل جولة تقلل معدل الخطأ إلى 1/4
- k جولة اختبار:معدل الخطأ النظري ≤ (1/4)^k، والفعلي أقل بكثير من ذلك
- الاختبار الحتمي:لـ n < 3,317,044,064,679,887,385,961,981، باستخدام مجموعة قواعد محددة {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} يمكن الحصول على نتيجة 100% دقيقة
الحالات الخاصة:
- الأعداد الأولية الصغيرة:2, 3, 5, 7 إلخ تُحسم مباشرة
- الأعداد الزوجية:كلها مركبة باستثناء 2
- أعداد Carmichael:أعداد تجتاز اختبار فيرما لكنها في الحقيقة مركبة (مثل 561)، يمكن لـ Miller-Rabin التعرف عليها بشكل صحيح