Thuật toán Miller-Rabin kiểm tra tính nguyên tố

Miller-Rabin là phương pháp nhanh kiểm tra nguyên tố số lớn. Thuật toán gọi là kiểm tra nguyên tố Rabin-Miller, quyết định số có phải nguyên tố giống các kiểm tra khác: Fermat, Solovay-Strassen.

Kiểm tra dựa trên đẳng thức hoặc nhóm đẳng thức đúng cho giá trị nguyên tố, do đó kiểm tra chúng có đúng cho số cần kiểm tra nguyên tố.

Thuật toán này là kiểm tra nguyên tố nổi tiếng nhất và dùng trong nhiều thư viện phần mềm dựa trên mã hóa RSA, ví dụ tốt nhất OpenSSL.

Miller-Rabin chứng minh số là hợp số (composite). Do đó gọi là kiểm tra hợp số (compositeness test) hơn là kiểm tra nguyên tố. Miller-Rabin nhận diện tất cả hợp số. Với mỗi hợp số n, tồn tại ít nhất 3/4 số a là chứng nhân hợp số của n.

Miller-Rabin là mở rộng đơn giản của Định lý Fermat nhỏ cho phép kiểm tra nguyên tố với xác suất lớn hơn nhiều so với Fermat.

Thuật toán: Mã giả Miller-Rabin:

Miller-Rabin-Test (n, a) // n là số; a là cơ sở {
    Tìm m và k sao cho n-1 = m × 2ᵏ
    T ← aᵐ mod n
    Nếu (T = ±1) trả về "nguyên tố"
    cho (i ← 1 đến k-1) // k-1 là số bước tối đa
    {
        T ← T² mod n
        nếu (T = ±1) trả về "hợp số"
        nếu (T = -1) trả về "nguyên tố"
    }
    trả về "hợp số"
}

Tồn tại chứng minh mỗi lần số qua kiểm tra Miller-Rabin, xác suất không phải nguyên tố là ¼. Nếu số qua m kiểm tra (m cơ sở khác nhau), xác suất không phải nguyên tố là (1/4)ᵐ.

Ví dụ: Áp dụng Miller-Rabin cơ sở 2 kiểm tra 341 hợp số hay không.

Giải pháp: Dùng Miller-Rabin kiểm tra 341:

Bước 1: 341-1 = 2² × 85. Do đó p=341, k=2, q=85

Bước 2: x = 2 (cho)

Bước 3: S = x^q mod p = 2⁸⁵ mod 341 = (2¹⁰) × 2⁵ mod 341 = 2¹⁰ mod 341 × 2¹³ mod 341 = 1 × 8192 mod 341 = 8192 mod 341 = 8

Bước 4: Vì 8 ≠ 1, chuyển bước tiếp.

Bước 5: j=1, S = x²q mod p = 2¹⁷⁰ mod 341 = (2²⁰)⁸ × 2¹⁰ mod 341 = 2²⁰ mod 341 × 2⁸ mod 341 × 2¹⁰ mod 341 = 1 × 256 × 1 = 256

256 ≠ 1 và kết quả không kết luận → 341 không phải hợp số (theo thuật toán này).

Ưu điểm

• Dùng kiểm tra số lớn nguyên tố.

• Nhanh hơn các kiểm tra nguyên tố khác, Miller-Rabin là lựa chọn cho nhiều ứng dụng mật mã.

• So với Euler và Solovay-Strassen, Miller-Rabin mạnh hơn và xác suất thất bại thấp hơn.

• Theo kiểm tra Fermat, quá nhiều "người nói dối" cho số Carmichael, xác suất lỗi gần 1, khuyết điểm này khắc phục trong Miller-Rabin.