Nguyên tắc thuật toán:
Miller-Rabin là một bài kiểm tra tính nguyên tố xác suất dựa trên sự mở rộng của định lý nhỏ Fermat. Với số lẻ n, viết n-1 là 2^r × d, sau đó kiểm tra xem nó có thỏa mãn:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Số vòng kiểm tra và độ chính xác:
- Kiểm tra xác suất:Chọn ngẫu nhiên một cơ số a; mỗi vòng kiểm tra giảm tỷ lệ lỗi xuống 1/4
- k vòng thử nghiệm:Tỷ lệ lỗi lý thuyết ≤ (1/4)^k, tỷ lệ lỗi thực tế thấp hơn nhiều
- Kiểm tra xác định:Đối với n < 3,317,044,064,679,887,385,961,981, sử dụng bộ cơ sở cụ thể {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} mang lại kết quả chính xác 100%
Trường hợp đặc biệt:
- Số nguyên tố nhỏ:Các số như 2, 3, 5, 7 được xác định trực tiếp
- Số chẵn:Tất cả các số chẵn ngoại trừ 2 đều là hợp số
- Số Carmichael:Các số vượt qua bài kiểm tra Fermat nhưng thực tế là hợp số (ví dụ: 561) có thể được xác định chính xác bởi Miller-Rabin