✨Kiểm tra Miller-Rabin

Kiểm tra Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố cũng như các thuật toán kiểm tra tính nguyên tố: Kiểm tra Fermat và Kiểm tra Solovay-Strassen. Nó được đề xuất đầu tiên bởi Gary L. Miller như một thuật toán tất định, dựa trên giả thiết Riemann tổng quát; Michael O. Rabin đã sửa chữa nó thành một thuật toán xác suất.

Khi sử dụng kiểm tra Miller-Rabin chúng ta căn cứ vào một mệnh đề Q(p, a) đúng với các số nguyên tố p và mọi số tự nhiên $a\; \backslash in\; A\; \backslash subset\; \backslash mathbb\; N$ và kiểm tra xem chúng có đúng với số n muốn kiểm tra và một số $a\; \backslash in\; A$ được chọn ngẫu nhiên hay không. Nếu mệnh đề Q(n, a) không đúng, tất yếu n không phải là số nguyên tố, còn nếu Q(n, a) đúng, số n có thể là số nguyên tố với một xác suất nào đó. Khi tăng số lần thử, xác suất để n là số nguyên tố tăng lên.

Tiêu chuẩn kiểm tra Q(n, a)

Căn bậc hai của 1 trong $\backslash mathbb\{Z\}\_p$

Trước hết là một bổ đề về căn bậc hai của đơn vị trong trường hữu hạn $\backslash mathbb\{Z\}\_p$, trong đó p là số nguyên tố. Chắc chắn rằng 1 và -1 luôn là các căn bậc hai của 1 theo module p. Chúng là hai căn bậc hai duy nhất của 1. Thật vậy, giả sử rằng x là một căn bậc hai của 1 theo module p. Khi đó: :$x^2\; \backslash equiv\; 1\backslash pmod\{p\}$ :$x^2-1\; \backslash equiv\; 0\backslash pmod\{p\}$ :$(x\; -\; 1)(x\; +\; 1)\; \backslash equiv\; 0\backslash pmod\{p\}$ Từ đó, $x-1$ hoặc $x+1$ là chia hết cho p.

Tiêu chuẩn Miller-Rabin

Bây giờ giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1 dưới dạng $2^s\; \backslash cdot\; m$, trong đó s là một số tự nhiên >=1 và m là số lẻ - Điều này nghĩa là ta rút hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập $\{1,\backslash \; 2,\backslash dots,\backslash \; p-1\}$.

Xét dãy số $x\_k=a^\{2^k.m\}$ với k=0,1,2,...,s. Khi đó $x$k = (x{k-1})^2, với k=1,2,...,s và $x\_s\; =\; a^\{p-1\}$

Từ định lý Fermat nhỏ: :$a^\{p-1\}\; \backslash equiv\; 1\backslash pmod\{p\}$ hay :$x$s \equiv 1\pmod{p} hay :$\{x${s-1^2 \equiv 1\pmod{p}. Do đó,hoặc $x${s-1}\equiv 1\pmod{p} hoặc $x${s-1}\equiv -1\pmod{p}.
Nếu $x${s-1}\equiv -1 \pmod p ta dừng lại, còn nếu ngược lại ta tiếp tục với $x${s-2}.

Sau một số hữu hạn bước

• hoặc ta có một chỉ số k, $0\; \backslash le\; k\; \backslash le\; s-1$ sao cho $x\_\{k\}\; \backslash equiv\; -1\; \backslash pmod\{p\}$,
• hoặc tới k = 0 ta vẫn có $x\_\{k\}\; \backslash equiv\; 1\; \backslash pmod\{p\}$. Ta có mệnh đề Q(p, a) như sau:

:Nếu p là số nguyên tố lẻ và $p-1\; =\; 2^s\; \backslash cdot\; m$ thì : _hoặc $x$k = a^{2^k \cdot m} \equiv 1 \pmod p,\ \forall \ k=0,\ 1,\ 2,\dots ,\ s _hoặc tồn tại k: $0\; \backslash le\; k\; \backslash le\; s$ sao cho $x$k=a^{2^k \cdot m} \equiv -1 \pmod p.

Số giả nguyên tố

• Theo định lý Fermat nhỏ, với số nguyên tố p ta có $\backslash forall\backslash \; a\; \backslash in\; \{1,\backslash \; 2,\backslash dots,\backslash \; p-1\}$: :$a^\{p-1\}\; \backslash equiv\; 1\; \backslash pmod\; p$
• Định nghĩa. Hợp số n thoả mãn $a^\{n-1\}\; \backslash equiv\; 1\; \backslash pmod\; n$ với a nào đó được gọi là số giả nguyên tố Fermat cơ sở a.
• Số Carmichael: Hợp số n là số giả nguyên tố Fermat với mọi cơ sở $a\; \backslash in\; \{1,\backslash \; 2,\backslash dots,\backslash \; n\}$, ƯCLN(a, n)=1 được gọi là số Carmichael.
• Định nghĩa: Hợp số n được gọi là số giả nguyên tố mạnh Fermat cơ sở a nếu nó thoả mãn mệnh đề Q(n, a).

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

Xác suất trả lời sai

Định lý: nếu n là hợp số dương lẻ thì trong các số $a\; \backslash in\; \{2,\backslash dots,\backslash \; n-1\}$ tồn tại không quá $\backslash frac\; \{n-1\}\; \{4\}$ cơ sở a để n là số giả nguyên tố mạnh Fermat.

Gọi A là biến cố "Số n là hợp số", B là biến cố "Kiểm tra Miller-Rabin trả lời n là số nguyên tố". Khi đó xác suất sai của kiểm tra này là xác suất để số n là hợp số trong khi thuật toán cho câu trả lời TRUE, nghĩa là xác suất điều kiện P(A|B).

Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE xảy ra với xác suất không vượt quá $\backslash frac\; 1\; 4$, nghĩa là $P(B|A)\; \backslash le\; \backslash frac\; 1\; 4$. Tuy nhiên để tính xác suất sai của kiểm tra Miller-Rabin cần tính xác suất diều kiện P(A|B). Dựa trên định lý về ước lượng số các số nguyên tố ta đưa ra ước lượng :: $P(A)\backslash approx\; 1\; -\; \backslash frac\; 2\; \{\backslash ln\; n\}\; \backslash approx\; \backslash frac\; \{\backslash ln\; n-2\}\; \{\backslash ln\; n\}$

Theo định lý Bayes trong lý thuyết xác suất ta có công thức để tính xác suất sai của kiểm tra Miller-Rabin là:

:: $P(A|B)\; =\; \backslash frac\; \{P(B|A)$P(A)}{P(B)} :::$=\; \backslash frac\; \{P(B|A)$P(A)}{P(B|A)P(A)+P(B|\overline A)P(\overline A)} Trong công thức này P(A) đã biết ở trên, $P(B|A)\; \backslash le\; \backslash frac\; 1\; 4$, còn $P(B|\backslash overline\; A)\; =\; 1$ vì khi n là số nguyên tố thì chắc chắn mệnh đề Q(n, a) là đúng và $P(\backslash overline\; A)=\; 1-\; P(A)=\; \backslash frac\; 2\; \{\backslash ln\; n\}$. Từ đó ::$P(A|B)\; =\; \backslash frac\; \{P(B|A)$P(A)}{P(B|A)P(A)+P(\overline A)} ::$P(A|B)\backslash approx\; \backslash frac\; \{P(B|A)$(\ln n-2)}{P(B|A)(\ln n-2)+2}

Kiểm tra Miller-Rabin lặp

Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân), nếu thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên 90%. Để giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác nhau, nếu n vượt qua 50 lần thử thì $P(B|A)\; \backslash le\; \backslash frac\; 1\; \{4^k\}$, khi thay vào công thức với 50 lần thử nếu cả 50 lần, phép thử đều "dương tính" thì xác suất sai giảm xuống chỉ còn là một số rất nhỏ không vượt quá $9\; \backslash cdot\; 10^\{-29\}$.