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 \in A \subset \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 \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 <math>\mathbb{Z}_p</math>
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 \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 \equiv 1\pmod{p}
:x^2-1 \equiv 0\pmod{p}
:(x - 1)(x + 1) \equiv 0\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 \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,\ 2,\dots,\ 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} \equiv 1\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 \le k \le s-1 sao cho x_{k} \equiv -1 \pmod{p},
* hoặc tới k = 0 ta vẫn có x_{k} \equiv 1 \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 \cdot m thì \forall\ a: 0 :
**hoặc <math>x_k = a^{2^k \cdot m} \equiv 1 \pmod p,\ \forall \ k=0,\ 1,\ 2,\dots ,\ s</math>*
**hoặc tồn tại k: <math>0 \le k \le s</math> sao cho <math>x_k=a^{2^k \cdot m} \equiv -1 \pmod p</math>*.

## Số giả nguyên tố
* Theo định lý Fermat nhỏ, với số nguyên tố *p* ta có \forall\ a \in \{1,\ 2,\dots,\ p-1\}:
: a^{p-1} \equiv 1 \pmod p
* **Định nghĩa**. Hợp số *n* thoả mãn  a^{n-1} \equiv 1 \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 \in \{1,\ 2,\dots,\ 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 \in \{2,\dots,\ n-1\} tồn tại không quá \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á \frac 1 4, nghĩa là P(B|A) \le \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)\approx 1 - \frac 2 {\ln n} \approx \frac {\ln n-2} {\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) = \frac {P(B|A)*P(A)}{P(B)}
:::= \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) \le \frac 1 4, còn P(B|\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(\overline A)= 1- P(A)= \frac 2 {\ln n}.
Từ đó
::P(A|B) = \frac {P(B|A)*P(A)}{P(B|A)P(A)+P(\overline A)}
::P(A|B)\approx \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) \le \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 \cdot 10^{-29}.

## Chú thích

## Tham khảo