หลักการอัลกอริทึม:
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 สามารถระบุได้ถูกต้อง