Kiểm tra Fermat

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

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

.

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

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

Còn nếu có số a

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