Mô phỏng thuật toán Kiểm tra nguyên tố Fermat

Fermat Primality Test · Nhóm: Số học

Kiểm tra nguyên tố xác suất bằng định lý nhỏ Fermat: nếu n nguyên tố thì a^(n−1) ≡ 1 (mod n).

Ý tưởng

Chọn một nhân chứng a rồi tính a^(n−1) mod n bằng bình phương liên tiếp: bình phương cơ số qua từng bit của số mũ, nhân vào kết quả tại các bit bằng 1.

So kết quả với 1: bằng 1 thì n có thể là nguyên tố, khác 1 thì n chắc chắn là hợp số.

Vì sao đúng

Định lý nhỏ Fermat đúng với mọi số nguyên tố; nếu đồng dư thức thất bại thì n không thể nguyên tố, còn nếu đạt thì n vượt qua một phép thử xác suất.

Mã Python

def fermat(n, a):
    x = pow(a, n - 1, n)   # a^(n-1) mod n
    return x == 1          # probably prime if True

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.