Miller Rabin là một cách tiếp cận nhanh để kiểm tra tính nguyên thủy của các số lượng lớn. Thuật toán này được gọi là bài kiểm tra tính nguyên thủy Rabin-miller và thuật toán này quyết định xem số có phải là số nguyên tố giống với các bài kiểm tra khác bao gồm Kiểm tra tính nguyên thủy Fermat và Kiểm tra tính nguyên thủy Solovay-Strassen hay không.
Kiểm tra này dựa trên sự bình đẳng hoặc nhóm các giá trị bằng nhau giữ giá trị đúng cho các giá trị nguyên tố, do đó kiểm tra xem chúng có đúng với số hay không, rằng nó được yêu cầu để kiểm tra tính nguyên tố.
Thuật toán này là thuật toán kiểm tra tính nguyên sơ hữu ích nhất đã biết và có thể được sử dụng trong các thư viện phần mềm khác nhau dựa trên mã hóa RSA và ví dụ tốt nhất là OpenSSL.
Miller Rabin xác nhận rằng con số là tổng hợp. Vì vậy, đây được gọi là kiểm tra tính tổng hợp hơn là kiểm tra tính nguyên thủy. Thử nghiệm Rabin của cối xay xác định tất cả các vật liệu tổng hợp. Với mỗi số tổng hợp n, có thể có ít nhất 3/4 (Miller Rabin) số a là nhân chứng của tổng hợp của n.
Miller Rabin là phần mở rộng tương đối đơn giản của Định lý Fermats little cho phép chúng ta kiểm tra tính nguyên thủy với xác suất lớn hơn nhiều so với Định lý Fermats little.
Thuật toán :Mã giả cho thử nghiệm Miller-Rabin -
Miller-Rabin-Test (n, a) // n is the number; a is the base
{
Find m and k such that n − 1 = m x 2k
T ← am mod n
If (T = ±1)return "a prime"
for (i ← 1 to k − 1) // k – 1 is the maximum number of steps
{
T ← T2 mod n
if (T = ±1) return "a composite"
if (T = −1) return "a prime"
}
return "a composite"
} Có i st là một bằng chứng rằng mỗi khi một số vượt qua phép thử Miller-Rabin, thì khả năng xảy ra rằng nó không phải là số nguyên tố là ¼. Nếu số đó vượt qua m phép thử (với m lần vượt qua), xác suất không phải là số nguyên tố là (1/4) m .
Ví dụ :Áp dụng Thuật toán Miller-Rabin bằng cách sử dụng cơ số 2 để kiểm tra xem số 341 có phải là hỗn hợp hay không.
Giải pháp :Sử dụng Thuật toán Miller-Rabin, chúng ta có thể kiểm tra số 341 như sau:
Bước1:341 - 1 =2 2 x 85. Như vậy p =341, k =2 và q =85
Bước 2:x =2 (đã cho)
Bước 3:S =x q mod p
=2 85 mod 341 =(2 10 ) x 2 5 mod 341 8
=2 10 mod 341 x 2 13 mod 341
=1 x 8192 mod 341 =8192 mod 341
=8
Bước 4:Như 8 ≠ 1, chúng ta chuyển sang bước tiếp theo.
Bước 5:Đối với j =1, S =x 2q mod p
=2 170 mod 341 =(2 20 ) 8 x 2 10 mod 341
=2 20 mod 341 x 2 8 mod 341 x 2 10 mod 341
=1 x 256 x 1 =256
Bây giờ, =256 ≠ 1
và kết quả là không thể kết luận
Vì vậy, 341 không phải là một số tổng hợp.
Ưu điểm
-
Thuật toán này có thể được sử dụng để kiểm tra các số cao về tính nguyên thủy.
-
Do có lợi thế về tốc độ khi so sánh với các bài kiểm tra tính sơ khai khác, bài kiểm tra Miller Rabin sẽ là bài kiểm tra được lựa chọn cho một số ứng dụng mật mã.
-
Khi so sánh với các bài kiểm tra Euler và Solovay-Strassen, Miller Rabin có tính năng động hơn và khía cạnh cơ bản là xác suất thất bại giảm xuống.
-
Theo thử nghiệm fermat, có quá nhiều người nói dối cho tất cả các Carmichaelnumbers n, xác suất sai là gần 1, nhược điểm này được ngăn chặn trongMiller Rabin.