Khóa học Python từ Cơ bản đến Nâng cao

Bài 16.5. Ứng dụng định lý Fermat với Python

Chào mừng các bạn trở lại với chuyên mục học Python và toán học! Hôm nay, chúng ta sẽ cùng nhau khám phá một định lý rất đẹp và hữu ích trong lý thuyết số, đó chính là định lý Fermat nhỏ, và xem cách chúng ta có thể vận dụng nó trong lập trình Python.

Định lý Fermat nhỏ là gì?

Định lý Fermat nhỏ phát biểu rằng:

Nếu p là một số nguyên tố và a là một số nguyên không chia hết cho p, thì:

a^{<strong><em>p</em></strong>-1} ≡ 1 (mod p)

Nói một cách đơn giản, nếu bạn lấy một số nguyên a, nâng nó lên lũy thừa (p-1) và sau đó chia cho số nguyên tố p, thì phần dư luôn luôn là 1 (miễn là a không phải là bội số của p).

Một dạng khác tương đương của định lý này là:

Nếu p là một số nguyên tố, thì với mọi số nguyên a:

a^{<strong><em>p</em></strong>} ≡ a (mod p)

Dạng này bao gồm cả trường hợp a là bội số của p, vì khi đó cả hai vế đều đồng dư với 0 theo modulo p.

Ứng dụng của định lý Fermat nhỏ

Định lý Fermat nhỏ có nhiều ứng dụng quan trọng trong toán học và khoa học máy tính, bao gồm:

• Kiểm tra tính nguyên tố: Mặc dù không hoàn hảo, nhưng định lý này có thể được sử dụng để kiểm tra sơ bộ xem một số có phải là số nguyên tố hay không.
• Tìm nghịch đảo modular: Chúng ta đã thấy ở bài trước, định lý Fermat nhỏ có thể giúp chúng ta tìm nghịch đảo modular một cách hiệu quả khi modulo là một số nguyên tố.
• Mật mã học: Định lý này là nền tảng cho một số thuật toán trong mật mã học, ví dụ như thuật toán RSA.

Ví dụ minh họa với Python

Hãy cùng xem xét một vài ví dụ cụ thể về cách ứng dụng định lý Fermat nhỏ trong Python.

Ví dụ 1: Kiểm tra tính nguyên tố (probabilistic test)

Chúng ta có thể sử dụng định lý Fermat nhỏ để thực hiện một kiểm tra tính nguyên tố có xác suất. Nếu chúng ta chọn một số a ngẫu nhiên không chia hết cho n, và a^<em>n</em>-1 mod n không bằng 1, thì chúng ta chắc chắn rằng n không phải là số nguyên tố. Tuy nhiên, nếu nó bằng 1, thì n có thể là số nguyên tố (hoặc là một số giả nguyên tố Carmichael).

import random

def is_prime_fermat(n, k=5):
    """Kiểm tra tính nguyên tố của n bằng định lý Fermat nhỏ (với k lần thử)."""
    if n <= 1:
        return False
    if n <= 3:
        return True
    for _ in range(k):
        a = random.randrange(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False
    return True

# Ví dụ sử dụng
numbers_to_test = [17, 91, 101, 203, 7]
for num in numbers_to_test:
    if is_prime_fermat(num):
        print(f"Số {num} có thể là số nguyên tố.")
    else:
        print(f"Số {num} chắc chắn không phải là số nguyên tố.")

Giải thích code:

• Hàm is_prime_fermat(n, k=5) nhận một số nguyên n và số lần thử k (mặc định là 5).
• Hàm xử lý các trường hợp cơ bản cho n nhỏ hơn hoặc bằng 3.
• Hàm thực hiện k lần thử. Trong mỗi lần thử, nó chọn một số nguyên a ngẫu nhiên trong khoảng từ 2 đến n-1.
• Hàm sử dụng hàm pow(a, n - 1, n) để tính (a^<em>n</em>-1) mod n một cách hiệu quả.
• Nếu kết quả không phải là 1, thì n chắc chắn không phải là số nguyên tố, và hàm trả về False.
• Nếu sau k lần thử mà không có lần nào kết quả khác 1, thì hàm trả về True, cho thấy n có thể là số nguyên tố.

Lưu ý quan trọng: Đây là một kiểm tra có xác suất. Có những số giả nguyên tố (số Carmichael) vẫn có thể vượt qua bài kiểm tra này.

Ví dụ 2: Tính nghịch đảo modular (khi modulo là số nguyên tố)

Như đã đề cập ở bài trước, nếu p là một số nguyên tố và a không chia hết cho p, thì nghịch đảo modular của a theo modulo p có thể được tính bằng công thức:

a^-1 ≡ a^{<strong><em>p</em></strong>-2} (mod p)

Chúng ta có thể dễ dàng triển khai điều này trong Python bằng hàm pow:

def modular_inverse_fermat(a, p):
    """Tính nghịch đảo modular của a theo modulo p bằng định lý Fermat nhỏ."""
    if pow(a, p - 1, p) != 1:
        return None  # a không có nghịch đảo modular theo modulo p
    return pow(a, p - 2, p)


# Ví dụ sử dụng
a = 3
p = 7
inverse = modular_inverse_fermat(a, p)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {p} là {inverse}")
else:
    print(f"{a} không có nghịch đảo modular theo modulo {p}.")

a = 5
p = 11
inverse = modular_inverse_fermat(a, p)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {p} là {inverse}")
else:
    print(f"{a} không có nghịch đảo modular theo modulo {p}.")

# Ví dụ trường hợp không tồn tại nghịch đảo (a là bội của p)
a = 7
p = 7
inverse = modular_inverse_fermat(a, p)
if inverse:
    print(f"Nghịch đảo modular của {a} theo modulo {p} là {inverse}")
else:
    print(f"{a} không có nghịch đảo modular theo modulo {p}.")

Giải thích code:

• Hàm modular_inverse_fermat(a, p) nhận số a và modulo p (phải là số nguyên tố).
• Hàm đầu tiên kiểm tra xem a^<em>p</em>-1 mod p có bằng 1 hay không. Nếu không, thì a không có nghịch đảo modular theo modulo p, và hàm trả về None.
• Nếu điều kiện trên đúng, hàm tính nghịch đảo modular bằng cách tính a^<em>p</em>-2 mod p sử dụng hàm pow(a, p - 2, p).

Ví dụ 3: Ứng dụng trong phép chia modular

Trong số học đồng dư, chúng ta không thể thực hiện phép chia trực tiếp. Tuy nhiên, chúng ta có thể thay thế phép chia cho một số bằng cách nhân với nghịch đảo modular của số đó. Sử dụng định lý Fermat nhỏ, nếu chúng ta muốn tính (a / b) mod p (với p là số nguyên tố và b không chia hết cho p), chúng ta có thể tính nó như sau:

(a / b) mod p ≡ (a × b^-1) mod p ≡ (a × b^<em>p</em>-2) mod p

def modular_division_fermat(a, b, p):
    """Thực hiện phép chia modular (a / b) mod p sử dụng định lý Fermat nhỏ."""
    inverse_b = modular_inverse_fermat(b, p)
    if inverse_b is None:
        raise ValueError("Không thể chia vì b không có nghịch đảo modular theo modulo p.")
    return (a * inverse_b) % p

# Ví dụ sử dụng
numerator = 10
denominator = 3
prime_modulus = 7

result = modular_division_fermat(numerator, denominator, prime_modulus)
print(f"({numerator} / {denominator}) mod {prime_modulus} = {result}")

numerator = 15
denominator = 5
prime_modulus = 11

result = modular_division_fermat(numerator, denominator, prime_modulus)
print(f"({numerator} / {denominator}) mod {prime_modulus} = {result}")

try:
    numerator = 10
    denominator = 7
    prime_modulus = 7
    result = modular_division_fermat(numerator, denominator, prime_modulus)
    print(f"({numerator} / {denominator}) mod {prime_modulus} = {result}")
except ValueError as e:
    print(f"Lỗi: {e}")

Giải thích code:

• Hàm modular_division_fermat(a, b, p) thực hiện phép chia a cho b theo modulo p.
• Hàm sử dụng hàm modular_inverse_fermat để tìm nghịch đảo modular của b theo modulo p.
• Nếu không tìm thấy nghịch đảo (ví dụ: b là bội của p), hàm sẽ raise một lỗi ValueError.
• Nếu tìm thấy nghịch đảo, hàm sẽ nhân a với nghịch đảo của b và lấy phần dư theo modulo p.

Kết luận

Định lý Fermat nhỏ là một công cụ mạnh mẽ và thanh lịch trong lý thuyết số với nhiều ứng dụng thực tế trong khoa học máy tính, đặc biệt là trong lĩnh vực mật mã học và số học đồng dư. Việc hiểu và biết cách áp dụng định lý này trong Python sẽ giúp bạn giải quyết nhiều bài toán thú vị và phức tạp.