Une procédure itérative basée sur la division qui calcule le plus grand commun diviseur (pgcd) de deux entiers en remplaçant successivement le plus grand nombre par son reste de la division par le plus petit jusqu'à ce que le reste soit zéro ; le dernier reste non nul est le pgcd.

Principe

Si a et b sont des entiers avec a = bq + r, alors pgcd(a,b) = pgcd(b,r). La répétition de cette étape diminue la taille des opérandes et garantit l'arrêt ; la forme étendue permet de remonter les rémainders pour obtenir des coefficients de Bézout exprimant le pgcd comme combinaison linéaire entière.

Démonstration

Calcul de pgcd(252, 198) : 252 = 198·1 + 54, 198 = 54·3 + 36, 54 = 36·1 + 18, 36 = 18·2 + 0, donc pgcd = 18. L'algorithme d'Euclide étendu conserve les combinaisons pour trouver x,y tels que 252x + 198y = 18.

Mauvaise application

Utiliser une division en virgule flottante sans contrôle exact des restes pour des pgcd entiers ou omettre la normalisation des signes et des zéros ; supposer que les étapes naïves d'Euclide suffisent à caractériser le coût en complexité pour des entiers très grands sans considérer le modèle d'arithmétique entière ou des algorithmes de multiplication sous-quadratiques.

Conséquence

Fournit une méthode efficace et à terminaison garantie pour calculer des pgcd, soutient les algorithmes d'inverses modulaires, la simplification de rationnels, le calcul d'ordres en cryptographie et en théorie des nombres, et constitue un bloc de construction pour les pgcd polynomiaux dans les domaines euclidiens.

Inversion

Contrasté avec les algorithmes de pgcd par soustraction répétée ou l'algorithme binaire de Stein : ces méthodes effectuent le même calcul de pgcd par des opérations élémentaires différentes et peuvent être préférables selon le matériel ou le modèle de complexité en bits.

Limite

S'applique dans les domaines euclidiens où existe un algorithme de division avec reste (entiers, polynômes univariés sur un corps) ; ne s'applique pas directement aux anneaux arbitraires dépourvus de fonction euclidienne, et les entrées doivent éviter le cas trivial des deux zéros.

Tension sémantique

Tension entre l'algorithme d'Euclide classique pas à pas et les implémentations modernes rapides : identiques en principe mais divergentes en complexité lorsqu'on emploie une arithmétique entière rapide ou des variantes sous-résultantes/polynomiales pour des contextes multivariés.

Synthèse

L'algorithme euclidien est le procédé itératif fondamental dans les domaines euclidiens qui réduit le calcul du pgcd à des restes plus petits, garantit l'arrêt, fournit des représentations de Bézout dans sa forme étendue et sous-tend de nombreuses constructions de base en théorie algorithmique des nombres et en algèbre.