Miller-Rabin Primality Test

Thuật toán Miller-Rabin là một phương pháp kiểm tra tính nguyên tố nhanh, dựa trên lý thuyết số và được sử dụng để xác định liệu một số lớn có phải là số nguyên tố hay không. Đây là một thuật toán xác suất, có nghĩa là nó có thể cho kết quả sai (các số giả nguyên tố), nhưng xác suất sai số là rất nhỏ nếu số lần kiểm tra tăng lên. Thuật toán này đặc biệt hữu ích khi làm việc với các số rất lớn, thường được sử dụng trong mật mã học và các ứng dụng liên quan đến bảo mật.

Ý tưởng chủ đạo

Thuật toán Miller-Rabin dựa trên nguyên lý của định lý Fermat nhỏ:

Nếu $p$ là số nguyên tố, thì ta có $a^p \equiv a (\bmod p)$. (Bạn có thể xem lại chứng minh của định lý này tại bài viết về thuật toán AKS.

Tuy nhiên, vấn đề là đối với một số tự nhiên $n$ bất kỳ thỏa mãn $a^n \equiv a (\bmod n)$ với $a$ cũng là số tự nhiên, thì chưa chắc $n$ đã là số nguyên tố. Nói cách khác, nếu $n$ vượt qua phép thử Fermat trên, vẫn tồn tại một khả năng nhỏ $n$ là hợp số. Từ đây, thuật toán Miller-Rabin mở rộng phép thử Fermat từ nhận xét:

• $a^n \equiv a (\bmod n) \iff a^{n-1} \equiv 1 (\bmod n)$

• Với mọi $n$, luôn có thể phân tích $n-1 = 2^s \times d$, với $d$ là một số lẻ

• Từ đó ta phân tích $a^{n-1} \equiv 1 (\bmod n)$ thành: $a^{n-1} - 1 = a^{2^s \times d} - 1 = (a^{2^{s-1} \times d} + 1)(a^{2^{s-2} \times d} + 1)\dots(a^d + 1)(a^d-1) \equiv 0 (\bmod n)$. Nếu $n$ là số nguyên tố thì phải tồn tại ít nhất một thừa số chia hết cho $n$.

Như vậy ta sẽ kiểm trả các điều kiện:

• Hoặc $n|(a^d-1) \implies a^d \equiv 1 (\bmod n)$

• Hoặc có ít nhất một thừa số $(a^{2^i\times d} + 1), 0\le i \le s-1$ chia hết cho $n$, hay $a^{2^i\times d} \equiv -1 (\bmod n)$

Nếu không thỏa cả 2 điều kiện trên thì $n$ chắc chắn là hợp số, ngược lại thì $n$ có khoảng $25 \%$ khả năng là một số nguyên tố. Như vậy, để chắc chắn hơn, ta có thể kiểm tra nhiều lần với nhiều giá trị $a$ khác nhau để tăng xác suất.

Thuật toán

Kiểm tra $n$ có phải số nguyên tố hay không, lưu ý rằng thuật toán dưới đây nếu trả về TRUE thì $n$ có thể là số nguyên tố, ngược lại nếu FALSE thì $n$ chắc chắc là hợp số.

• Phân tích $n = 2^s\times d +1$

• Chọn số ngẫu nhiên $a \in [2, n-1]$:

  • Nếu $a^d \bmod n = 1$: return TRUE

• Cho $i: 1 \to k-1:$

  • Nếu $a^{2^i\times d} \bmod n = 1$: return TRUE

• Return FALSE

Demo