Algorithme d'Euclide étendu
13966
30735684
2008-06-17T17:18:26Z
Proz
92456
/* L'algorithme */ syntaxe
L''''algorithme d'Euclide étendu''' est une variante de l'[[algorithme d'Euclide]] qui permet, à partir de deux entiers ''a'' et ''b'', de calculer non seulement leur [[plus grand commun diviseur]] (PGCD), mais aussi un de leurs couples de [[Identité de Bézout|coefficients de Bézout]] (deux entiers ''u'' et ''v'' tels que ''au'' + ''bv'' = PGCD(''a'',''b'')).
Quand ''a'' et ''b'' sont [[premiers entre eux]] : ''u'' est alors l'inverse pour la multiplication de ''a'' [[modulo]] ''b'', ce qui est un cas particulièrement utile. Comme l'algorithme d'Euclide, l'algorithme étendu se généralise aux anneaux euclidiens, par exemple aux [[polynôme]]s à une variable sur un [[corps]].
== Exemple introductif ==
Considérons par exemple le calcul du PGCD de 120 et 23 avec l'algorithme d'Euclide :
{| class="wikitable" align="center"
|-
|120 ÷ 23 = 5 reste 5
|-
|23 ÷ 5 = 4 reste 3
|-
|5 ÷ 3 = 1 reste 2
|-
|3 ÷ 2 = 1 reste 1
|-
|2 ÷ 1 = 2 reste 0
|}
Dans ce cas, le reste obtenu à l'avant dernière ligne donne le PGCD égal à 1 ; c'est-à-dire que 120 et 23 sont premiers entre eux. Maintenant présentons autrement les divisions précédentes :
{|class="wikitable" align="center"
|Reste||=||Dividende||-||Quotient||×||Diviseur
|-
|{{fond or}}|5||=
||<font color="aa0000">'''120'''</font>
||-||5||×
||<font color="aa0000">'''23'''</font>
|-
|{{fond bleu}}|3||=
||<font color="aa0000">'''23'''</font>
||-||4||×
|{{fond or}}|5
|-
|{{fond vert}}|2||=
|{{fond or}}|5
||-||1||×
|{{fond bleu}}|3
|-
|1||=
|{{fond bleu}}|3
||-||1||×
|{{fond vert}}|2
|-
|0||=
|{{fond vert}}|2
||-||2||×||1
|}
Observons que 120 et 23 apparaissent sur les deux premières lignes. D'autre part, la valeur la plus à droite dans chaque ligne (à partir de la 2{{e}} ligne du tableau) est le reste de la ligne précédente, et le dividende est — dans chaque égalité à partir de la 3{{e}} ligne — le reste obtenu deux lignes plus haut. Nous pouvons ainsi calculer progressivement chaque reste successif comme combinaison linéaire des deux valeurs initiales 120 et 23.
Cependant cette méthode n'est pas la plus efficace. On écrit d'abord ces calculs de façon à faire apparaître un algorithme plus direct :
{|class="wikitable" align="center"
!r !! colspan="12"| !! = !! u !! ×!! a !! + !! v !!× !! b
|-
|{{fond bleu}}|120|| || || || || || || || || || || || || = ||{{fond vert}}|1||× ||120|| - ||{{fond vert}}|0||× ||23
|-
|{{fond bleu}}|23|| || || || || || || || || || || || || = ||{{fond vert}}|0||× ||120|| + ||{{fond vert}}|1||× ||23
|-
|{{fond bleu}}|5|| = ||120|| - ||bgcolor="#ffffd9"|5||×||23|| || || || || || || = ||{{fond vert}}|1||× ||120|| - ||{{fond vert}}|5||× ||23
|-
|{{fond bleu}}|3|| = ||23|| - ||bgcolor="#ffffd9"|4||×||5|| = ||1×23 || - ||4||×||(1×120 - 5×23) || = ||{{fond vert}}|-4||×||120|| + ||{{fond vert}}|21||×||23
|-
|{{fond bleu}}|2|| = ||5|| - ||bgcolor="#ffffd9"|1||×||3|| = ||(1×120 - 5×23)|| - ||1||×||(-4×120 + 21×23)|| = ||{{fond vert}}|5||× ||120|| - ||{{fond vert}}|26||×||23
|-
|{{fond bleu}}|1|| = ||3|| - ||bgcolor="#ffffd9"|1||×||2|| = ||(-4×120 + 21×23) || - ||1||×||(5×120 - 26×23) || = ||{{fond vert}}|-9||×||120|| + ||{{fond vert}}|47||×||23
|}
Remarquons que la dernière ligne donne 1 = -9×120 + 47×23, et nous fournit exactement ce que nous voulons : ''u'' = -9 et ''v'' = 47. Ceci signifie que -9 est l'inverse pour la multiplication de 120 modulo 23, parce que 1 = -9 × 120 (mod 23).
On a en bleu les calculs successifs qui conduisent au pgcd par reste de la division des deux nombres précédents (algorithme d'Euclide ordinaire). On a noté en jaune les quotients correspondants. Les deux colonnes vertes donnent les calculs successifs qui aboutissent aux coefficients de Bezout (''u'' et ''v''). On peut vérifier que ces coefficients se calculent à partir des deux coefficients les précédant dans la même colonne, à l'aide des quotients de la colonne jaune : les formules sont précisées dans le tableau du paragraphe suivant.
== 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.
{|class="wikitable" align="center"
|-
! r
!u
!v
|-
|r<sub>0</sub> = a || u<sub>0</sub> = 1 || v<sub>0</sub> = 0
|-
|r<sub>1</sub> = b || u<sub>1</sub> = 0 || v<sub>1</sub> = 1
|-
|… || … || …
|-
|r<sub>i-1</sub> || u<sub>i-1</sub> || v<sub>i-1</sub>
|-
|r<sub>i</sub> || u<sub>i</sub> || v<sub>i</sub>
|-
|r<sub>i-1</sub> - (r<sub>i-1</sub>÷r<sub>i</sub>)r<sub>i</sub> || u<sub>i-1</sub> - (r<sub>i-1</sub>÷r<sub>i</sub>)u<sub>i</sub> || v<sub>i-1</sub> - (r<sub>i-1</sub>÷r<sub>i</sub>)v<sub>i</sub>
|-
|… || … || …
|-
|r<sub>n</sub>= pgcd(a,b)|| u<sub>n</sub> = u || v<sub>n</sub> = v
|-
|0 || u<sub>n+1</sub> || v<sub>n+1</sub>
|}
On obtient donc une suite (''r''<sub>''i''</sub>, ''u''<sub>''i''</sub>, ''v''<sub>''i''</sub>), récurrente d'ordre 2, nécessairement finie car la suite (''r''<sub>''n''</sub>) 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 ''r''<sub>''n+1''</sub>=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 (''r''<sub>''n''</sub>, ''u''<sub>''n''</sub>, ''v''<sub>''n''</sub>) 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 ''r''<sub>''i''</sub>= ''au''<sub>''i''</sub> + ''bv''<sub>''i''</sub> (voir le tableau). On en déduit que tout diviseur de ''a'' et ''b'' divise les ''r''<sub>''i''</sub>, combinaisons linéaires de ''a'' et ''b'', en particulier ''r''<sub>''n''</sub>. Enfin on remarque que si un entier divise ''r''<sub>''i''+1</sub> et ''r''<sub>''i''</sub>, il divise ''r''<sub>''i''-1</sub> (voir le tableau) ; comme ''r''<sub>''n''</sub> divise bien ''r''<sub>''n''+1</sub> = 0 et ''r''<sub>''n''</sub>, on en déduit par récurrence qu'il divise tous les ''r''<sub>''i''</sub>, en particulier ''r''<sub>0</sub> = ''a'' et ''r''<sub>1</sub> = ''b'', c'est donc bien le pgcd de ''a'' et ''b''.
On obtient un algorithme très simple en calculant deux lignes successives du tableau ci-dessus. Par exemple par cette fonction, définie récursivement, calcule le pgcd et les deux coefficients de Bezout :
:eucl(x, u, v, 0, u, v') = (x, u, v)
:eucl(x, u, v, x', u', v') = eucl(x', u', v', x - (x÷x')*x', u - (x÷x')*u', v - (x÷x')*v') pour x' ≠ 0
On a alors :
:eucl(a, 1, 0, b, 0, 1) = (pgcd(a,b),u,v) avec pgcd(a,b)= a*u + b*v.
On en déduit directement un algorithme impératif, utilisant une boucle while.
On peut remarquer qu'en justifiant l'algorithme, on a du même coup montré l'identité de Bezout pour les entiers.
Les calculs de ''u''<sub>''i''</sub> et ''v''<sub>''i''</sub> dépendent tous deux de celui des ''r''<sub>''i''</sub>, mais sont indépendants entre eux. On peut donc simplifier cet algorithme en ne calculant que (''r''<sub>''i''</sub>, ''u''<sub>''i''</sub>). 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.
Voici en [[Javascript]] l'implémentation de l'algorithme d'Euclide étendu qui devrait fonctionner dans la plupart des [[navigateur web|navigateurs]] :
<source lang='Javascript'>
// Ce programme ne fonctionne qu'avec des entiers naturels
// demande les données à l'utilisateur et convertit les chaînes de caractères en entiers
var a = parseInt(prompt("Entrer un entier naturel a",0))
var b = parseInt(prompt("Entrer un entier naturel b",0))
// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;
// Initialisations. On laisse invariant p*a0 + q*b0 = a et r*a0 + s*b0 = b.
p = 1; q = 0;
r = 0; s = 1;
// La boucle principale:
while (b != 0) {
c = a % b;
quotient = Math.floor(a/b); //Javascript n'a pas d'opération de division entière.
a = b;
b = c;
nouveau_r = p - quotient * r; nouveau_s = q - quotient * s;
p = r; q = s;
r = nouveau_r; s = nouveau_s;
}
// Affiche le résultat.
alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)
</source>
----
== Complexité de l'algorithme ==
L'algorithme d'Euclide étendu à 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 (''r''<sub>''i''</sub>) 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 (''r''<sub>''i''</sub>) dans l'ordre inverse, soit (''r''<sub>''n'' + 1 - ''i''</sub>), et en remplaçant à chaque étape le quotient par 1, on reconnait la [[suite de Fibonacci]], à la différence que si le premier terme, ''r''<sub>''n'' + 1 - 0</sub>, est bien 0, le second, ''r''<sub>''n'' + 1 - 1</sub>, est le PGCD de ''a'' et ''b''. En notant ''d'' = pgcd(''a'',''b''), et (f<sub>''i''</sub>) la suite de Fibonacci, on obtient donc :
:''r''<sub>''n'' + 1 - ''i''</sub> ≥ ''d''.f<sub>''i''</sub>
et donc (théorème de Lamé) :
:''r''<sub>1</sub> = ''b'' ≥ ''d''.f<sub>''n''</sub> 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 f<sub>''n''</sub> ~ [(1+√5)/2]<sup>''n''</sup> (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.
==Liens internes==
[[Identité de Bezout]]
== Bibliographie ==
* Michel Demazure 1997 -- ''Cours d'Algèbre : primalité, divisibilité, codes.'', Cassini - Paris, ISBN 2-84225-000-1
[[Catégorie:Algorithme|Euclide]]
[[ca:Algorisme d'Euclides ampliat]]
[[de:Erweiterter euklidischer Algorithmus]]
[[en:Extended Euclidean algorithm]]
[[lt:Išplėstinis Euklido algoritmas]]
[[nl:Uitgebreid algoritme van Euclides]]
[[pt:Algoritmo de Euclides estendido]]
[[vi:Giải thuật Euclid mở rộng]]