Algorithme étendu

On apprend au collège à calculer le P G C D de deux nombres en décomposant ces 2 nombres en produits de facteurs premiers. Mais lorsque les nombres sont trop grands on utilise l'algorithme d'Euclide:

 

Si a et b sont deux entiers avec par exemple a>=b, si r est le reste de a par b, alors le pgcd de a et b vaut le pgcd de b et r.

Après avoir effectué les divisions successives, on retiendra que le dernier reste non nul est le PGCD de a et b.

 

Le PGCD de 541 et 222 est 1 , les deux nombres sont premiers entre eux

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.

La dernière ligne donne 1 = 103×541 + -251×222, et nous fournit exactement les coefficients de Bezout : u = 103 et v = -251. Ceci signifie que 103 est l'inverse pour la multiplication de 541 modulo 222, parce que 1 = 103 × 541 (mod 222). De même -251 est l'inverse, pour la multiplication modulo 541, de 222 ,parce que 1 = -251 × 222 (mod 541).

Application : Le cryptage RSA

L'école d'Athènes

Les modernes