Extended Euclidean Algorithm
L'algorithme d'Euclide étendu calcule gcd(a,b) tout en trouvant les coefficients de Bézout x, y satisfaisant ax+by=gcd(a,b).
Objectif
Calculer les inverses modulaires et résoudre les équations diophantiennes linéaires ; un outil fondamental en théorie des nombres et cryptographie.
Mécanisme
Il maintient les coefficients en remontant l'algorithme d'Euclide : gcd(a,b)=gcd(b, a mod b), et en remontant x=y_prev, y=x_prev-floor(a/b)*y_prev. Complexité O(log min(a,b)).
Cas d’usage
- Calcul d'inverses modulaires
- Génération de clés RSA
- Équations diophantiennes linéaires