Thuật toán Fermat trong Python

Thuật toán Fermat là một thuật toán tìm số nguyên tố được đặt theo tên của nhà toán học người Pháp Pierre de Fermat. Thuật toán này hoạt động bằng cách kiểm tra xem một số nguyên dương n có phải là số nguyên tố hay không bằng cách kiểm tra tính đúng đắn của định lý Fermat nhỏ.

Định lý Fermat nhỏ: Nếu p là một số nguyên tố và a là một số nguyên dương nhỏ hơn p, thì a^(p-1) ≡ 1 mod p.

Các bước của thuật toán Fermat để kiểm tra tính nguyên tố của một số nguyên dương n như sau:

1. Chọn một số nguyên dương a ngẫu nhiên nhỏ hơn n.
2. Tính a^(n-1) mod n.
3. Nếu kết quả là 1, thì n có thể là số nguyên tố.
4. Nếu kết quả khác 1, thì n không phải là số nguyên tố.
5. Lặp lại các bước trên với các giá trị a khác nhau cho đến khi bạn hoàn thành một số lần kiểm tra được chỉ định.

Nếu n không phải là số nguyên tố, thuật toán Fermat không đảm bảo tìm được điểm đầu tiên trong dãy dấu hiệu của n không phải là số nguyên tố. Tuy nhiên, nếu n chịu ảnh hưởng bởi lỗi sẽ có rất ít các giá trị a cho phép a^(n-1) ≡ 1 mod n, cho nên thuật toán này thường được sử dụng để tìm kiếm các lỗi của hàm băm hoặc kiểm tra độ bảo mật của các hệ mã hóa.

Dưới đây là cài đặt thuật toán Fermat để kiểm tra tính nguyên tố của một số nguyên dương n bằng ngôn ngữ Python:

import random

def is_prime_fermat(n, k=5):
    # Kiểm tra trường hợp cơ sở
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False

    # Kiểm tra tính đúng đắn của định lý Fermat nhỏ k lần
    for i in range(k):
        a = random.randint(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False

    return True

Trong đó, tham số đầu tiên là số nguyên dương n cần kiểm tra tính nguyên tố, và tham số thứ hai (mặc định là 5) là số lần kiểm tra định lý Fermat nhỏ với các giá trị a ngẫu nhiên khác nhau. Hàm này trả về True nếu n là số nguyên tố và False nếu n không phải là số nguyên tố.

Chú ý rằng, dù thuật toán Fermat khá hiệu quả trong việc kiểm tra tính nguyên tố của các số lớn, nhưng không phải là hoàn toàn chính xác. Khi sử dụng thuật toán này, cần cân nhắc và kiểm tra kết quả một cách cẩn thận để đảm bảo tính chính xác của kết quả.