Algorithme d'Euclide étendu - Définition
La liste des auteurs de cet article est disponible ici.
Complexité de l'algorithme
L'algorithme d'Euclide étendu a la même structure que l'algorithme d'Euclide : le nombre d'itérations est le même, seul change le nombre d'opérations à chaque itération.
Pour évaluer le nombre de pas d'itérations, c'est-à-dire l'entier noté n + 1 ci-dessus, on suppose tout d'abord que a ≥ b, pour que la suite (ri) soit décroissante dès le début. On remarque alors que le quotient est, par construction, toujours supérieur ou égal à 1. En prenant la suite (ri) dans l'ordre inverse, soit (rn + 1 - i), et en remplaçant à chaque étape le quotient par 1, on reconnait la suite de Fibonacci, à la différence que si le premier terme, rn + 1 - 0, est bien 0, le second, rn + 1 - 1, est le PGCD de a et b. En notant d = pgcd(a, b), et (fi) la suite de Fibonacci, on obtient donc :
- rn + 1 - i ≥ d.fi
et donc (théorème de Lamé) :
- r1 = b ≥ d.fn où le nombre d'itérations de l'algorithme est n+1.
Ce nombre est d'ailleurs effectivement atteint pour a et b deux nombres consécutifs de la suite de Fibonacci, ou multiples de ceux-ci : la suite de Fibonacci étant croissante le quotient est bien 1 à chaque étape..
Comme fn ~ [(1+√5)/2]n (voir l'article sur la suite de Fibonacci), le nombre d'itérations est donc en log b, à une constante multiplicative près.
Il n'est guère réaliste, sauf à ne manipuler que de petits nombres, de considérer que le coût des opérations effectuées à chaque itération, division, multiplication et soustraction, est constant. Si l'on suppose que celui-ci est linéaire en la taille de l'entrée (en binaire), on obtient une complexité en O(log²(sup(a, b)), c'est-à-dire, à une constante multiplicative près, celle de l'algorithme d'Euclide ordinaire.
L'algorithme
On présente, sous forme de suite, le calcul du PGCD et des coefficients de Bezout pour deux entiers naturels a et b. Le quotient (entier !) de x par y est noté x ÷ y. Pour a=120 et b=23, on vérifiera que le calcul conduit aux trois colonnes r, u et v de l'exemple.
| r | u | v |
|---|---|---|
| r0 = a | u0 = 1 | v0 = 0 |
| r1 = b | u1 = 0 | v1 = 1 |
| … | … | … |
| ri-1 | ui-1 | vi-1 |
| ri | ui | vi |
| ri-1 - (ri-1÷ri)ri | ui-1 - (ri-1÷ri)ui | vi-1 - (ri-1÷ri)vi |
| … | … | … |
| rn= pgcd(a, b) | un = u | vn = v |
| 0 | un+1 | vn+1 |
On obtient donc une suite (ri, ui, vi), récurrente d'ordre 2, nécessairement finie car la suite (rn) est strictement décroissante au plus tard à partir du second rang, et parce que l'on ne peut diviser par 0. On a posé n+1 le premier indice tel que rn+1=0 qui est donc l'indice maximal d'un élément de la suite. On peut justifier cette construction, plus précisément justifier que l'avant dernier terme de la suite, soit (rn, un, vn) fournit bien le pgcd de a et b et deux coefficients de Bezout u et v vérifiant pgcd(a, b)= ua + bv. En effet, il est immédiat, par récurrence à partir des deux termes précédents, qu'à chaque étape ri= aui + bvi (voir le tableau). On en déduit que tout diviseur de a et b divise les ri, combinaisons linéaires de a et b, en particulier rn. Enfin on remarque que si un entier divise ri+1 et ri, il divise ri-1 (voir le tableau) ; comme rn divise bien rn+1 = 0 et rn, on en déduit par récurrence qu'il divise tous les ri, en particulier r0 = a et r1 = b, c'est donc bien le pgcd de a et b.
Au cours de la démonstration, on a jamais eu besoin de supposer le théorème de Bezout, et de fait, celle-ci fournit également une démonstration de ce théorème pour deux entiers naturels et on le déduit immédiatement pour deux entiers relatifs.
La définition par récurrence de la suite (ri, ui, vi) fournit directement un algorithme très simple pour calculer les coefficients de Bezout. L'algorithme, va calculer à chaque étape deux triplets consécutifs de la suite (deux lignes consécutives du tableau ci-dessus). Par exemple on obtient le pgcd et les deux coefficients de Bezout par la définition récursive suivante :
eucl(r, u, v, 0, u', v') = (r, u, v) eucl(r, u, v, r', u', v') = eucl(r', u', v', r - (r÷r')*r', u - (r÷r')*u', v - (r÷r')*v') pour r' ≠ 0
On a alors eucl(a, 1, 0, b, 0, 1) = (pgcd(a, b), u, v) avec pgcd(a, b)= a*u + b*v.
De façon à peu près équivalente, on a l'algorithme impératif suivant, qui utilise une boucle while.
Entrée: a, b entiers (naturels) Sortie: r entier (naturel) et u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v Initialisation: r:= a, r':= b, u:= 1, v:= 0, u':= 0, v':= 1 q, rs, us, vs quotient et variables de stockage intermédiaires les égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle. tant que (r' ≠ 0) faire q:= r÷r' rs:= r, us:= u, vs:= v r:= r', u:= u', v:= v' r':= rs -q *r', u' = us - q*u', v' = vs -q*v' fait renvoyer (r, u, v)
Les calculs de ui et vi dépendent tous deux de celui des ri, mais sont indépendants entre eux. On peut donc simplifier cet algorithme en ne calculant que (ri, ui). Cela suffit si on cherche l'inverse de a modulo b (cas où a et b sont premiers entre eux). On peut de toute façon calculer ensuite directement le second coefficient à partir du premier.
