เครื่องคำนวณการทดสอบความเป็นจำนวนเฉพาะมิลเลอร์-ราบิน

เกี่ยวกับเครื่องคำนวณนี้

การทดสอบมิลเลอร์-ราบินตรวจสอบความเป็นจำนวนเฉพาะโดยเขียน n − 1 ในรูป 2ˢ·d โดยที่ d เป็นจำนวนคี่ แล้วทดสอบว่าฐานพยาน a สอดคล้องกับ aᵈ ≡ 1 (mod n) หรือ a^(2ʳ·d) ≡ −1 (mod n) สำหรับบาง r < s หรือไม่ พยานเพียงตัวเดียวให้ผลเชิงความน่าจะเป็นเท่านั้น แต่การทดสอบกับชุดฐานพยานคงที่ขนาดเล็กที่พิสูจน์แล้ว (เช่น 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) ทำให้การทดสอบแน่นอนสำหรับจำนวนเต็มทุกจำนวนที่น้อยกว่าประมาณ 3.18 × 10²³ ซึ่งเกินกว่าที่แอปพลิเคชันส่วนใหญ่ต้องการมาก

นักเข้ารหัสลับและนักพัฒนาซอฟต์แวร์ใช้การทดสอบแบบนี้พอดีเมื่อสร้างจำนวนเฉพาะผู้สมัครขนาดใหญ่สำหรับกุญแจ RSA หรือ Diffie-Hellman ส่วนนักศึกษาวิทยาการคอมพิวเตอร์ใช้ดูจากตัวเลขจริงว่าเหตุใดมิลเลอร์-ราบินจึงขยายขนาดได้ดีกว่าการหารทดลองมากเมื่อตรวจสอบว่าจำนวนเต็มขนาดใหญ่เป็นจำนวนเฉพาะหรือไม่