Bài 8: Thuật toán kiểm tra số nguyên tố lớn Miller-Rabin

Trong ngành mật mã học, các thuật toán mã hoá công khai đều cần sử dụng các số nguyên tố lên tới hơn 512 bits. Có một số phương pháp để sinh số nguyên tố và các phương pháp đó đều dựa theo thuật toán kiểm tra tính nguyên tố của một số nguyên.

Các loại thuật toán kiểm tra số nguyên tố được chia làm 2 loại:

• Thuật toán tất định: cho biết chính xác một số nguyên có phải là số nguyên tố không; thuật toán đúng nhưng chậm.
• Thuật toán xác suất: cho biết xác suất là số nguyên tố của một số nguyên.

Bài viết này sẽ giới thiệu một phương pháp kiểm tra số nguyên tố theo thuật toán xác suất là Phương pháp kiểm tra số nguyên tố Miller-Rabin

Giải thuật kiểm tra Miller-Rabin

Thuật toán Miller_Rabin kiểm tra tính nguyên tố của một số nguyên p:

TEST(p)
    Tìm k, q với k> 0, q lẻ thỏa mãn p = 2kq + 1
    Chọn số ngẫu nhiên a trong khoảng [2, p - 1]
    If aq mod p = 1 Then 
        return "p có thể là số nguyên tố";
    For j= 0 to k-1 do
        If a2j*q mod p = 1 Then 
            return "p có thể là số nguyên tố";
    return "p không phải là số nguyên tố";

Ví dụ 1: kiểm tra số p = 29

29 = 2² * 7 + 1 do đó k = 2, q = 7

• Nếu chọn a = 10: 10⁷ mod 29 = 17 do đó ta sẽ tiếp tục tính (10⁷)² mod 29 = 28 thủ tục kiểm tra sẽ trả về “có thể là số nguyên tố”.
• Nếu chọn a = 2: 2⁷ mod 29 = 12 do đó ta sẽ tiếp tục tính (2⁷)² mod 29 = 28 thủ tục cũng sẽ trả về “có thể là số nguyên tố”.
• Vì vậy, nếu chỉ thử một vài giá trị a, ta chưa thể kết luận gì về tính nguyên tố của p. Tuy nhiên nếu thử hết các giá trị a từ 2 đến 28 ta đều nhận được kết quả “có thể là số nguyên tố”. Vì vậy có thể chắc chắn rằng 29 là số nguyên tố.

Ví dụ 2: kiểm tra số p = 221

221 = 2² * 55 + 1 do đó k = 2, q = 55.

• Nếu chọn a = 5: 5⁵⁵ mod 221 = 112 do đó ta sẽ tiếp tục tính (5⁵⁵)² mod 29 = 168, do đó thủ tục kiểm tra sẽ trả về “không phải là số nguyên tố”. Điều này đúng vì 221 = 13 x 17.
• Tuy nhiên nếu chọn a = 21: 21⁵⁵ mod 221 = 200 do đó ta sẽ tiếp tục tính (21⁵⁵)² mod 29 = 220, lúc này thủ tục sẽ trả về ‚có thể là số nguyên tố‛. Nghĩa là trong một số trường hợp của a, thuật Miller-Rabin không xác định được tính nguyên tố của 221.

Xác suất sai và nguyên tắc kiểm tra

Người ta đã tính được xác suất để trong trường hợp p là hợp số, thuật toán MillerRabin đưa ra khẳng định ‚không phải là số nguyên tố‛ là 75%. Trong 25% còn lại, Miller-Rabin không xác định được p nguyên tố hay hợp số. Do đó nếu chúng ta áp dụng thuật toán t lần (mỗi lần với các giá trị a khác nhau) thì xác suất không xác định (trong cả t lần) là (0.25) t . Với t bằng 10, xác suất trên là rất bé, nhỏ hơn 0.000001.

Tóm lại nguyên tắc kiểm tra tính nguyên tố của số nguyên p thực hiện như sau:

• Thực hiện thuật toán Miller-Rabin 10 lần với 10 số a ngẫu nhiên khác nhau.
• Nếu cả 10 lần thuật toán cho ra kết quả “có thể là số nguyên tố”, thì ta khẳng định p là số nguyên tố.
• Chỉ cần một lần thuật toán cho ra kết quả “không phải là số nguyên tố”, thì ta khẳng định p là hợp số.

Ví dụ 3: p = 41, 41= 2³*5 + 1 do đó k = 3, q = 5, p-1 = 40 .

Ví dụ 4: p = 133, 133 = 2² * 33 + 1 do đó k = 2, q = 33, p-1 = 132.

Tuy tính toán hơi phức tạp nhưng thuật toán Miller-Rabin là thuật toán kiểm tra số nguyên tố hiệu quả nhất, thực hiện nhanh nhất trong các thuật toán kiểm tra số nguyên tố đã biết.

Nam.Name.Vn