Cálculo Eficiente do Inverso Multiplicativo Modular em Python

O inverso multiplicativo modular é um conceito fundamental na teoria dos números e na criptografia. É um número que, quando multiplicado por outro número e tomado módulo um módulo dado, produz um resultado de 1. Este artigo explora vários algoritmos eficientes para calcular o inverso multiplicativo modular em Python, comparando sua eficiência e aplicabilidade.

Sumário

1. Abordagem Iterativa Ingênua
2. Exponenciação Modular (Pequeno Teorema de Fermat)
3. Algoritmo Euclidiano Estendido
4. Conclusão

1. Abordagem Iterativa Ingênua

Esta abordagem direta itera por possíveis inversos até encontrar um que satisfaça a condição. Embora simples de entender, sua complexidade de tempo O(m) a torna altamente ineficiente para módulos grandes.

def modular_inverse_naive(a, m):
    """
    Calcula o inverso multiplicativo modular usando uma abordagem iterativa ingênua.

    Args:
        a: O número para o qual encontrar o inverso.
        m: O módulo.

    Returns:
        O inverso multiplicativo modular de a módulo m, ou None se ele não existir.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Exemplo de uso
a = 3
m = 11
inverso = modular_inverse_naive(a, m)
print(f"O inverso multiplicativo modular de {a} módulo {m} é: {inverso}")  # Saída: 4

2. Exponenciação Modular (Pequeno Teorema de Fermat)

Quando o módulo m é primo, o Pequeno Teorema de Fermat fornece uma solução eficiente. Ele afirma que a^p-1 ≡ 1 (mod p) para qualquer inteiro a não divisível por p. Portanto, o inverso é a^p-2 (mod p), eficientemente computável usando exponenciação modular. Este método tem uma complexidade de tempo de O(log m).

def modular_exponentiation(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        exp >>= 1
        base = (base * base) % mod
    return res

def modular_inverse_fermat(a, p):
  if p <= 1:
    raise ValueError("p deve ser um número primo maior que 1")
  return modular_exponentiation(a, p - 2, p)

# Exemplo de uso (p é primo)
a = 3
p = 11
inverso = modular_inverse_fermat(a, p)
print(f"O inverso multiplicativo modular de {a} módulo {p} é: {inverso}")  # Saída: 4

3. Algoritmo Euclidiano Estendido

O Algoritmo Euclidiano Estendido é o método mais geral e eficiente, aplicável a qualquer módulo. Ele encontra o máximo divisor comum (MDC) de dois números e o expressa como uma combinação linear desses números. Se o MDC é 1, o inverso modular existe e é facilmente obtido. Este algoritmo também possui uma complexidade de tempo de O(log m).

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modular_inverse_euclidean(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # Inverso não existe
    else:
        return x % m

# Exemplo de uso
a = 3
m = 11
inverso = modular_inverse_euclidean(a, m)
print(f"O inverso multiplicativo modular de {a} módulo {m} é: {inverso}")  # Saída: 4

a = 5
m = 12
inverso = modular_inverse_euclidean(a, m)
print(f"O inverso multiplicativo modular de {a} módulo {m} é: {inverso}")  # Saída: None

4. Conclusão

Este artigo apresentou três algoritmos para calcular o inverso multiplicativo modular. A abordagem ingênua é simples, mas ineficiente. O Pequeno Teorema de Fermat oferece uma solução eficiente para módulos primos. O Algoritmo Euclidiano Estendido é o método mais versátil e eficiente, aplicável a qualquer módulo onde o inverso exista, tornando-o a escolha preferida para a maioria das aplicações, especialmente em criptografia.