Calcul efficace de l’inverse multiplicatif modulaire en Python

L’inverse multiplicatif modulo est un concept fondamental en théorie des nombres et en cryptographie. C’est un nombre qui, lorsqu’il est multiplié par un autre nombre et pris modulo un module donné, donne un résultat de 1. Cet article explore plusieurs algorithmes efficaces pour calculer l’inverse multiplicatif modulo en Python, en comparant leur efficacité et leur applicabilité.

Table des matières

1. Approche itérative naive
2. Exponentiation modulaire (Petit théorème de Fermat)
3. Algorithme d’Euclide étendu
4. Conclusion

1. Approche itérative naive

Cette approche simple itère sur les inverses possibles jusqu’à ce qu’elle en trouve un qui satisfait la condition. Bien que simple à comprendre, sa complexité temporelle de O(m) la rend très inefficace pour les grands modules.

def modular_inverse_naive(a, m):
    """
    Calcule l'inverse multiplicatif modulo en utilisant une approche itérative naive.

    Args:
        a: Le nombre pour lequel trouver l'inverse.
        m: Le module.

    Returns:
        L'inverse multiplicatif modulo de a modulo m, ou None s'il n'existe pas.
    """
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

# Exemple d'utilisation
a = 3
m = 11
inverse = modular_inverse_naive(a, m)
print(f"L'inverse multiplicatif modulo de {a} modulo {m} est : {inverse}")  # Output: 4

2. Exponentiation modulaire (Petit théorème de Fermat)

Lorsque le module m est premier, le Petit théorème de Fermat fournit une solution efficace. Il stipule que a^p-1 ≡ 1 (mod p) pour tout entier a non divisible par p. Par conséquent, l’inverse est a^p-2 (mod p), calculable efficacement en utilisant l’exponentiation modulaire. Cette méthode a une complexité temporelle 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 doit être un nombre premier supérieur à 1")
  return modular_exponentiation(a, p - 2, p)

# Exemple d'utilisation (p est premier)
a = 3
p = 11
inverse = modular_inverse_fermat(a, p)
print(f"L'inverse multiplicatif modulo de {a} modulo {p} est : {inverse}")  # Output: 4

3. Algorithme d’Euclide étendu

L’algorithme d’Euclide étendu est la méthode la plus générale et la plus efficace, applicable à tout module. Il trouve le plus grand commun diviseur (PGCD) de deux nombres et l’exprime comme une combinaison linéaire de ces nombres. Si le PGCD est 1, l’inverse modulo existe et est facilement obtenu. Cet algorithme possède également une complexité temporelle 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  # L'inverse n'existe pas
    else:
        return x % m

# Exemple d'utilisation
a = 3
m = 11
inverse = modular_inverse_euclidean(a, m)
print(f"L'inverse multiplicatif modulo de {a} modulo {m} est : {inverse}")  # Output: 4

a = 5
m = 12
inverse = modular_inverse_euclidean(a, m)
print(f"L'inverse multiplicatif modulo de {a} modulo {m} est : {inverse}")  # Output: None

4. Conclusion

Cet article a présenté trois algorithmes pour calculer l’inverse multiplicatif modulo. L’approche naive est simple mais inefficace. Le Petit théorème de Fermat offre une solution efficace pour les modules premiers. L’algorithme d’Euclide étendu est la méthode la plus polyvalente et la plus efficace, applicable à tout module où l’inverse existe, ce qui en fait le choix préféré pour la plupart des applications, notamment en cryptographie.