Principe de l'algorithme :
L'algorithme d'Euclide étendu calcule non seulement le plus grand commun diviseur pgcd(a, m) de deux entiers a et m, mais trouve également les entiers x et y tels que ax + my = gcd(a, m)。
Ceci est une application de l'identité de Bézout (équation de Bézout).
Étapes de l'algorithme :
- Algorithme d'Euclide :Calculer pgcd(a, m) en utilisant l'algorithme de division, en enregistrant le quotient et le reste à chaque étape.
- Substitution inverse :En partant de la dernière étape, substituer en arrière pour exprimer chaque reste comme une combinaison linéaire de a et m.
- Résolution des coefficients :Finalement, obtenir les coefficients x et y satisfaisant ax + my = pgcd(a, m).
Inverse modulaire :
Lorsque pgcd(a, m) = 1 (c'est-à-dire que a et m sont premiers entre eux), un inverse multiplicatif de a modulo m existe, noté a-1 mod m. Dans ce cas, x est l'inverse modulaire, satisfaisant a × x ≡ 1 (mod m)。
Si x est négatif, il doit être ajusté à une valeur positive : x' = x mod m.
Applications :
- Cryptographie :Le calcul de la clé privée dans l'algorithme RSA nécessite de trouver l'inverse modulaire.
- Problèmes de théorie des nombres :Résoudre les congruences linéaires de la forme ax ≡ b (mod m).
- Combinatoire :Calcul combinatoire modulaire (théorème de Lucas, etc.)
- Programmation compétitive :Calcul rapide d'inverse modulaire pour éviter les problèmes de précision liés à la division
Complexité temporelle :
O(log min(a, m)), identique à l'algorithme d'Euclide
Identité de Bézout :
Pour tous entiers a et m, il existe des entiers x et y tels que ax + my = pgcd(a, m). Ces coefficients x et y peuvent être calculés efficacement à l'aide de l'algorithme d'Euclide étendu.