Algorithme D'Euclide Étendu

Algorithme d'Euclide étendu

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 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. L'algorithme d'Euclide étendu fournit également une méthode efficace non seulement pour déteminer quand une équation diophantienne ax+by = c possède une solution, ce que permet déjà l'algorithme d'Euclide simple, mais également pour en calculer dans ce cas une solution particulière, dont on déduit facilement la solution générale.

Comme l'algorithme d'Euclide, l'algorithme étendu se généralise aux anneaux euclidiens, tels celui des polynômes à une variable sur un corps commutatif. De même que pour les entiers, il permet alors de calculer l'inverse d'un polynôme modulo un polynôme avec lequel il est premier, et donc des calculs d'inverse dans les anneaux ou corps construits par quotient sur l'anneau des polynômes : corps de rupture, corps finis

Sommaire

Exemple introductif

Considérons par exemple le calcul du PGCD de 120 et 23 avec l'algorithme d'Euclide :

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 :

Reste = Dividende - Quotient × Diviseur
5 = 120 - 5 × 23
3 = 23 - 4 × 5
2 = 5 - 1 × 3
1 = 3 - 1 × 2
0 = 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 2e ligne du tableau) est le reste de la ligne précédente, et le dividende est — dans chaque égalité à partir de la 3e 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 :

r = u × a + v × b
120 = 1 × 120 - 0 × 23
23 = 0 × 120 + 1 × 23
5 = 120 - 5 × 23 = 1 × 120 - 5 × 23
3 = 23 - 4 × 5 = 1×23 - 4 × (1×120 - 5×23) = -4 × 120 + 21 × 23
2 = 5 - 1 × 3 = (1×120 - 5×23) - 1 × (-4×120 + 21×23) = 5 × 120 - 26 × 23
1 = 3 - 1 × 2 = (-4×120 + 21×23) - 1 × (5×120 - 26×23) = -9 × 120 + 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). De même 47 est l'inverse, pour la multiplication modulo 120, de 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.

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 x = pgcd(a, b) et x = 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.

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 ab, 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 - id.fi

et donc (théorème de Lamé) :

r1 = bd.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.

Généralisations

Les entiers relatifs

On pourrait facilement ramener le calcul du pgcd et des coefficients de Bezout de deux entiers relatifs, à celui de deux entiers naturels. L'algorithme indiqué s'applique cependant sans aucune modification aux entiers relatifs. Il suffit de remarquer que, dans la division euclidienne, c'est alors la valeur absolue du reste qui est plus petite que la valeur absolue du diviseur, ce qui assure la terminaison de l'algorithme. En effet, si on définit de la même façon à partir de deux entiers relatifs a et b la suite (ri, ui, vi), c'est cette fois-ci la suite des valeurs absolues des ri qui est strictement décroissante à partir du second rang. On montre de façon identique que rn, l'avant dernier terme de la suite, est un diviseur commun de a et de b, multiple de tout diviseur commun de a et de b, c'est-à-dire un plus grand (au sens de la divisibilité) diviseur commun de a et b, et donc le pgcd de a et b ou son opposé. Pour les mêmes raisons les nombres un, vn satisfont l'identité de Bezout.

Les anneaux euclidiens

L'anneau des entiers relatifs est un anneau euclidien, et ce sont les seules propriétés utiles pour l'algorithme d'Euclide étendu. Celui-ci se généralise donc directement aux anneaux euclidiens, et se justifie de la même façon. Seules changent les opérations de base, et la division. Comme pour les entiers relatifs, il n'y a pas forcément unicité, et l'algorithme détermine un plus grand diviseur commun, les autres s'en déduisent par multiplication par une unité (1 et -1. pour les entiers relatifs). De même que pour les entiers, il peut être légèrement modifié quand le pgcd est défini de façon unique grâce à une condition supplémentaire, de façon à ce que le résultat vérifie celle-ci.

Liens internes

Bibliographie

  • Michel Demazure 1997 -- Cours d'Algèbre : primalité, divisibilité, codes., Cassini - Paris, ISBN 2-84225-000-1
Ce document provient de « Algorithme d%27Euclide %C3%A9tendu ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme D'Euclide Étendu de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme d'Euclide etendu — Algorithme d Euclide étendu 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… …   Wikipédia en Français

  • Algorithme d'euclide étendu — 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 coefficients de Bézout (deux …   Wikipédia en Français

  • Algorithme d'Euclide étendu — 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 coefficients de Bézout (deux …   Wikipédia en Français

  • Algorithme d'Euclide (mathématiques élémentaires) — Algorithme d Euclide L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide.… …   Wikipédia en Français

  • Algorithme d'Euclide — L algorithme d Euclide est un algorithme permettant de déterminer le plus grand commun diviseur (P.G.C.D.) de deux entiers dont on ne connaît pas la factorisation. Il est déjà décrit dans le livre VII des Éléments d Euclide. Dans la tradition… …   Wikipédia en Français

  • algorithme — [ algɔritm ] n. m. • 1554; lat. médiév. Algorithmus, n. pr. latinisé de l ar. Al Khawarizmi (cf. algèbre), pris pour nom commun, égalt sous la forme algorismus ♦ Vx Système de numération décimale emprunté des Arabes. ♢ Mod. Math. Suite finie,… …   Encyclopédie Universelle

  • Algorithme De Shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… …   Wikipédia en Français

  • Algorithme de shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… …   Wikipédia en Français

  • Algorithme de Shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”