Công cụ kiểm tra số nguyên tố Miller-Rabin

Giới thiệu về công cụ này

Phép thử Miller-Rabin kiểm tra tính nguyên tố bằng cách viết n − 1 thành 2ˢ·d với d lẻ, rồi kiểm tra xem một cơ sở nhân chứng a có thỏa aᵈ ≡ 1 (mod n) hoặc a^(2ʳ·d) ≡ −1 (mod n) với một r < s nào đó hay không. Một nhân chứng đơn lẻ chỉ cho kết quả xác suất, nhưng kiểm tra với một tập cơ sở nhân chứng cố định nhỏ đã được chứng minh (ví dụ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) làm cho phép thử trở nên xác định với mọi số nguyên dưới khoảng 3,18 × 10²³ — vượt xa những gì hầu hết ứng dụng từng cần.

Nhà mật mã học và lập trình viên phần mềm dùng đúng kiểu phép thử này khi sinh các ứng viên số nguyên tố lớn cho khóa RSA hoặc Diffie-Hellman, còn sinh viên khoa học máy tính dùng nó để thấy trên các số thực vì sao Miller-Rabin mở rộng quy mô tốt hơn nhiều so với phép chia thử khi kiểm tra một số nguyên lớn có phải số nguyên tố hay không.