Cálculo eficiente del inverso multiplicativo modular en Python

El inverso multiplicativo modular es un concepto fundamental en la teoría de números y la criptografía. Es un número que, cuando se multiplica por otro número y se toma el módulo de un módulo dado, produce un resultado de 1. Este artículo explora varios algoritmos eficientes para calcular el inverso multiplicativo modular en Python, comparando su eficiencia y aplicabilidad.

Tabla de contenido

1. Enfoque iterativo ingenuo
2. Exponenciación modular (Teorema pequeño de Fermat)
3. Algoritmo euclidiano extendido
4. Conclusión

1. Enfoque iterativo ingenuo

Este enfoque sencillo itera a través de posibles inversos hasta que encuentra uno que satisface la condición. Si bien es fácil de entender, su complejidad temporal de O(m) lo hace altamente ineficiente para módulos grandes.

def modular_inverse_naive(a, m):
    """
    Calcula el inverso multiplicativo modular usando un enfoque iterativo ingenuo.

    Args:
        a: El número para el cual encontrar el inverso.
        m: El módulo.

    Returns:
        El inverso multiplicativo modular de a módulo m, o None si no existe.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Ejemplo de uso
a = 3
m = 11
inverso = modular_inverse_naive(a, m)
print(f"El inverso multiplicativo modular de {a} módulo {m} es: {inverso}")  # Salida: 4

2. Exponenciación modular (Teorema pequeño de Fermat)

Cuando el módulo m es primo, el Teorema pequeño de Fermat proporciona una solución eficiente. Establece que a^p-1 ≡ 1 (mod p) para cualquier entero a no divisible por p. Por lo tanto, el inverso es a^p-2 (mod p), calculable eficientemente usando exponenciación modular. Este método tiene una complejidad temporal 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 debe ser un número primo mayor que 1")
  return modular_exponentiation(a, p - 2, p)

# Ejemplo de uso (p es primo)
a = 3
p = 11
inverso = modular_inverse_fermat(a, p)
print(f"El inverso multiplicativo modular de {a} módulo {p} es: {inverso}")  # Salida: 4

3. Algoritmo euclidiano extendido

El Algoritmo euclidiano extendido es el método más general y eficiente, aplicable a cualquier módulo. Encuentra el máximo común divisor (MCD) de dos números y lo expresa como una combinación lineal de esos números. Si el MCD es 1, el inverso modular existe y se obtiene fácilmente. Este algoritmo también tiene una complejidad temporal 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  # El inverso no existe
    else:
        return x % m

# Ejemplo de uso
a = 3
m = 11
inverso = modular_inverse_euclidean(a, m)
print(f"El inverso multiplicativo modular de {a} módulo {m} es: {inverso}")  # Salida: 4

a = 5
m = 12
inverso = modular_inverse_euclidean(a, m)
print(f"El inverso multiplicativo modular de {a} módulo {m} es: {inverso}")  # Salida: None

4. Conclusión

Este artículo presentó tres algoritmos para calcular el inverso multiplicativo modular. El enfoque ingenuo es simple pero ineficiente. El Teorema pequeño de Fermat ofrece una solución eficiente para módulos primos. El Algoritmo euclidiano extendido es el método más versátil y eficiente, aplicable a cualquier módulo donde exista el inverso, lo que lo convierte en la opción preferida para la mayoría de las aplicaciones, especialmente en criptografía.