Малая теорема Ферма — фундаментальный результат теории чисел, имеющий множество приложений в различных областях, включая криптографию. В этой статье блога мы углубимся в эту теорему и рассмотрим несколько методов на примерах кода, чтобы продемонстрировать ее практическое применение.

Что такое Малая теорема Ферма?
Малая теорема Ферма гласит, что если p — простое число, а a — любое положительное целое число, меньшее p, то a, возведенное в степень p (a^p), соответствует a по модулю п. Математически это можно представить следующим образом: a^p ≡ a (mod p).

Метод 1: модульное возведение в степень
Одним из наиболее распространенных применений Малой теоремы Ферма является модульное возведение в степень. Этот метод позволяет нам эффективно вычислять большие степени числа по модулю другого числа. Вот пример кода на Python:

def modular_exponentiation(base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent // 2
        base = (base * base) % modulus
    return result

Метод 2: проверка на простоту
Малая теорема Ферма представляет собой вероятностный тест на простоту, известный как тест на простоту Ферма. Его можно использовать для быстрого определения того, является ли данное число простым или составным. Вот пример кода на Python:

import random
def is_prime(n, k=5):
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True
    for _ in range(k):
        a = random.randint(2, n - 2)
        if modular_exponentiation(a, n - 1, n) != 1:
            return False
    return True

Метод 3: шифрование RSA
Малая теорема Ферма лежит в основе алгоритма шифрования RSA, который широко используется в защищенной связи. Теорема гарантирует, что процессы шифрования и дешифрования в RSA математически обоснованы. Вот упрощенный пример шифрования RSA с использованием Малой теоремы Ферма:

# Key generation
p = 17
q = 23
n = p * q
phi = (p - 1) * (q - 1)
# Choose a value for e (public key)
e = 7
# Compute the modular inverse of e modulo phi (private key)
d = modular_exponentiation(e, -1, phi)
# Encryption
plaintext = 42
ciphertext = modular_exponentiation(plaintext, e, n)
# Decryption
decrypted_text = modular_exponentiation(ciphertext, d, n)
print("Plaintext:", plaintext)
print("Ciphertext:", ciphertext)
print("Decrypted Text:", decrypted_text)

Малая теорема Ферма — мощный инструмент в теории чисел, который можно применять в модульном возведении в степень, проверке на простоту и криптографии. Поняв и реализовав эти методы, вы сможете использовать потенциал теоремы в различных вычислительных задачах. Независимо от того, работаете ли вы над алгоритмами шифрования или исследуете свойства простых чисел, Малая теорема Ферма, несомненно, станет ценным дополнением к вашему математическому арсеналу.