sur Internet
sur ground418

L'algorithme Euclidien étendu

Sommaire:

Histoire
Algo euclidien
Algo euclidien étendu
Références



Euclid était un mathématicien grec qui a vécu au 3e siècle avant JC. Il a principalement travaillé sur la géométrie et a posé les base de la méthode par axiome en mathématique avec son livre Les éléments. La page wiki de ce monsieur Euclid est une bonne référence pour en apprendre un peu plus sur son histoire [1]. Euclid a élaboré un algorithme qui permet de calculer le plus grand commun diviseur (g.c.d.) de 2 entiers, disons q et r. Il se formule de comme suit:

---

Algorithme euclidien

	Si |q| < |r| alors t := q;
			q := r;
			r := t;
					
	tant que r n'égal pas 0
		faire	t := reste(q,r);
			q := r;
			r := t;
			
	retourner q; 

---

Dans cet algorithme, la fonction reste() calcule le reste de la division de q / r. La plupart des langages de programmation utilisent le symbole % (modulo). Un code PHP est disponible pour vous illustrer l'algorithme en action. L'algorithme peut aussi être utilisé pour des polynômes, il suffit de remplacer la comparaison des valeurs absolues (Si |q| < |r|) par une comparaison du degré des polynômes.

Nous pouvons facilement utiliser cet algorithme pour déterminer à chaque étape, la représentation linéaire de q et r par rapport à leurs valeurs initiales.

---

Algorithme euclidien étendu [2]

	si |q| < |r| alors t := q;
			q := r;
			r := t;
			Q := [0,1];
			R := [1,0];
		sinon	Q := [1,0];
			R := [0,1];

	tant que r n'égal pas 0
		faire	t := reste(q,r);
			T := Q - ⌊ q/r ⌋R;
			q := r;
			r := t;
			Q := R;
			R := T;

	retourner q et Q;

---

La première valeur retournée est le g.c.d. de q et r (disons que p est le g.c.d), la seconde est le couple [a,b] tel que p = aq + br. Cette égalité est appelée l'identité de Bézout, d'après le mathématicien français Étienne Bézout. Ce dernier algorithme est beaucoup utilisé dans l'arithmétique modulaire. Effectivement, nous pouvons prouver que la division mod(n) par un entier a est possible en utilisant l'algorithme g.c.d. puisque b = 1/a mod(n) existe si et seulement si gcd(a, n) = 1. [3]

La division étant possible, avec l'algorithme étendu, nous savons qu'il existe un x et un y qui forme l'équation ax + ny = 1. En réduisant l'équation mod(n), nous obtenons ax = 1mod(n). Alors le 1/a mod(n) peut être calculé à l'aide de l'algorithme Euclidien étendu avec un nombre de divisions de l'ordre de O(log n).

Références


[1] http://en.wikipedia.org/wiki/Euclid

[2] Computer Algebra, systems and algorithms for algebraic computation, deuxième édition par J.H. Davenport, Y. Siret, E. Tournier, 1993, pages 231-232.

[3] Euclid's GCD Algorithm - http://www.cs.berkeley.edu/~vazirani/s99cs170/notes/lec3.pdf