Kiểm tra Fermat

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Kiểm tra Fermat là một thuật toán xác suất kiểm tra một số tự nhiên là hợp số hay là số nguyên tố xác suất.

Khái niệm[sửa | sửa mã nguồn]

Định lý nhỏ Fermat phát biểu rằng nếu p là số nguyên tố và 1 \le a < p, thì

a^{p-1} \equiv 1 \pmod{p}.

Nếu ta muốn kiểm tra số n có là nguyên tố không, ta lấy ngẫu nhiên các số a' và kiểm tra xem đẳng thức trên có đúng không. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đẳng thức đúng với nhiều giá trị của a, ta có thể nói rằng n là số nguyên tố với xác suất nào đó, hay là một số giả nguyên tố (pseudoprime).

Có thể phép thử sẽ cho ta một kết quả sai.

Số a

a^{n-1} \equiv 1 \pmod{n}

trong khi n là hợp số được gọi là một giả Fermat.

Còn nếu có số a

a^{n-1} \not\equiv 1 \pmod{n}

thì a được xem như một bằng chứng Fermat chứng tỏ n là hợp số.

Thuật toán và thời gian thi hành[sửa | sửa mã nguồn]

Thuật toán có thể viết như sau:

Inputs: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm tra
Output: hợp số nếu n là hợp số, nếu không nguyên tố xác suất
repeat k times:
lấy a ngẫu nhiên trong [1, n − 1]
if an − 1 mod n ≠ 1 then
return composite
return probably prime

Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán là O(k × log3n), ở đó k là số lần kiểm tra với mỗi số a ngãu nhiên, và n là giá trị ta muốn kiểm tra.

Khả năng vận dụng[sửa | sửa mã nguồn]

Có khá nhiều giá trị của n là các số Carmichael mà với tất cả các giá trị của a sao cho ƯCLN(a,n)=1 là giả Fermat. Mặc dù các số Carmichael là rất hiếm, nhưng phép thử Fermat rất ít được dùng so với các phương pháp khác như kiểm tra Miller-Rabin hay kiểm tra Solovay-Strassen.

Nói chung, nếu n không là số Carmichael thì ít nhất một nửa các số

a\in(\mathbb{Z}/n\mathbb{Z})^*

là bằng chứng Fermat. Để chứng minh điều này, giả sử a là một bằng chứng Fermat và a1, a2,..., as là giả Fermat. Khi đó

(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}

và do đó tất cả a × ai for i = 1, 2,..., s là bằng chứng Fermat.

Xem thêm[sửa | sửa mã nguồn]