Chương 1 TỔNG QUAN VỀ MẬT MÃ HỌC
4. Một số thuật toán kiểm tra số nguyên tố
4.3 Thuật toán Miller-Rabin
Thuật toán Miller Rabin là phi n bản sửa đổi của thuật toán Fermat sử dụng ý tưởng đơn giản trình bày dưới đây để tạo ra kiểm tra thi n về hợp số rất mạnh. Nó thay thế thuật toán Solovay-Strassen như là một chọn lựa đầu ti n để kiểm tra xác suất vì hiệu quả cao hơn và xác suất chính xác cũng cao hơn.
Định lý 4.3.1: Nếu x2 = 1 mod n có nghiệm không tầm thường, thì n là hợp số.
Giống như giả nguy n tố, thuật toán kiểm tra an-1 = 1 mod n và phân loại là số giả nguy n tố nếu được. Cũng như vậy, tuy nhi n, nó cũng kiểm tra căn bậc hai không tầm thường (nontrivial square root) của 1 mod n bằng cách tính an-1 theo
một cách ri ng. Đầu ti n, nó biểu diễn n-1 = u.2t, u là số lẻ. Sau đó viết an-1 = au.2t = (au)2t được tính bằng cách bình phương li n tiến au tổng cộng t lần. Thuật toán đầu tiên tính au sử dụng bình phương li n tiếp (ordinary binary exponentiation), sau đó bình phương nó t lần, giữ lại giá trị hiện tại(cur) và giá trị cuối cùng (last) ở mỗi bước. Nếu cur = 1, thì last là thặng dư bậc hai (square root) của 1 mod n. Nếu last khác 1, hoặc -1, thì nó là bất thặng dư bậc hai (nontrivial square root) của 1 mod n, và do đó n là hợp số. Nếu mr-witness(a, n) trả về đúng (true), thì a là cơ sở cho n là hợp số.
Kiểm tra Miller-Rabin chỉ đơn giản chạy thuật toán mr-witness với k lần ngẫu nhi n chọn giá trị a. Nếu bất kỳ giá trị nào chứng tỏ n là hợp số thì n là hợp số, ngược lại n là số nguy n tố với xác suất nào đó:
Thuật toán thể hiện mạnh hơn kiểm tra Fermat, bởi vì nó sử dụng định lý ở tr n để tăng cường kiểm tra hợp số. Định lý tiếp theo trình bày bằng chứng là những thay đổi tạo ra dấu hiệu cho thấy kiểm tra xác suất số nguy n tố tốt hơn.
Định lý 4.3.2: nếu n là hợp số lẻ, thì số bằng chứng chứng tỏ n là hợp số ít nhất bằng 3/4 (n-1) [CM. 24].
Theo định lý này nếu n là hợp số thì ít nhất 75% khả năng chứng tỏ là hợp số với bất kỳ giá trị ngẫu nhi n của cơ sở. Kiểm tra Miller – Rabin sẽ chỉ có lỗi nếu nó chọn k cơ sở kiểm tra từ tập hợp bằng chứng sai. Xác suất sai được phát biểu bởi hệ quả của định lý dưới đây:
Hệ quả 4.3.3: Nếu thuật toán Miller – Rabin với tham số n và k phân loại n là nguyên tố, thì xác suất sai nhiều nhất là (1/4)k.
Cũng như thuật toán Solovay–Strassen, xác suất sai độc lập với n. Ví dụ, nếu chọn k = 25, thì Miller – Rabin rất có khả nẳng tìm ra một bằng chứng cho n là hợp
số, dù chỉ là một. Nếu nó không tìm được bằng chứng, thì xác suất n là nguy n tố với xác suất sai là (1/4)25 = 10-15.
Thuật toán mr-witness thực hiện với độ phức tạp thời gian O(log n), về bản chất nó tính an-1 mod n bằng phương pháp bình phương li n tiếp. Nghĩa là độ phức tạp của nó tương đương với thuật toán giả nguy n tố của kiểm tra Fermat, nhưng kiểm tra thi n về hợp số mạnh hơn. Thuật toán Miller–Rabin thực hiện mr-witness k lần, n n độ phức tạp thời gian là O(k . logn). Kiểm tra Miller–Rabin cho khả năng phân loại sai là (1/4)k với độ phức tạp O(k. log n).
Vì đây là thuật toán xác suất tìm số nguy n tố tốt nhất hiện nay, n n trong luận văn này xin trình bày một số ví dụ minh hoạ
Ví dụ 1: Lấy n = 91 = 7.13, n-1=90=21.45, n n s=1. Chú ý 91 là hợp số
(a). Chọn ngẫu nhi n cơ sở a=10. Bắt đầu với b=1045 mod 91 = 90. Do đó thuật toán kết luận là số nguy n tố. Tuy nhi n, chúng ta biết rằng 91 không phải là số nguy n tố, vậy 10 là một cơ sở cho kết luận sai.
(b). Chọn ngẫu nhi n cơ sở a=29. Bắt đầu với b=2945 mod 91 = 1. Do đó thuật toán lại trả về kết quả đúng (true), và 29 cũng là một cơ sở cho kết luận sai.
(c). Cuối cùng, chọn a=2 bắt đầu với b=245 mod 91 = 57. Ở đây thuật toán không thể vào vòng lặp ( bởi vì s-1=0), thuật toán đến dòng 14, và từ đây cho kết quả sai (false).
Vậy 91 được xác định là hợp số.
Ví dụ 2: Lấy n=101, n-1=100=22.25, n n s=2. Chú ý 101 là số nguy n tố (a). Giả sử a=17, có b=100, và thuật toán kết luận là số nguy n tố.
(b). Giả sử a=19, có b=1, và thuật toán kết luận là số nguy n tố.
(c). Giả sử a=29,có b=91, n n vào vòng lặp. Tính b=912 mod 101, kết quả là 100, thuật toán kết luận là số nguy n tố.
(d). Giả sử a=3. Có b=10, n n vào vòng lặp. Tính b=102 mod 101, kết quả là 100, thuật toán kết luận là số nguy n tố.
Ở đây, 4 lần kiểm tra đều cho kết quả là số nguy n tố (với xác suất nào đó). Xác suất sai cho cho kết quả là <= 1/44 = 1/256.
Vậy theo thuật toán thì 101 là số nguy n tố với xác suất là 1-1/256 = 0.9961.