L'algorithme d'Euclide étendu
Description
Quel est le plus grand diviseur commun (=pgcd) de 126 et 462? On apprend au collège à calculer ce pgcd en décomposant les 2 nombres en produits de facteurs premiers, et en réunissant les facteurs en commun. Cette méthode n'est plus envisageable quand les entiers deviennent grands (plusieurs centaines de chiffres décimaux), car la factorisation est un problème difficile. On calcule donc le pgcd en appliquant l'algorithme d'Euclide, qui repose sur la constation suivante :
Si $a$ et $b$ sont deux entiers avec par exemple $a\geq b$, si $r$ est le reste dans la division de $a$ par $b$, alors $\textrm{pgcd}(a,b)=\textrm{pgcd}(b,r)$.
On effectue donc des divisions euclidiennes, jusqu'à ce qu'on trouve un reste nul. Le dernier reste non nul est le pgcd de a et b.Ex : On souhaite calculer le pgcd de 255 et 141.
- 255=1×141+114
- 141=1×114+27
- 114=4×27+6
- 27=4×6+3
- 6=2×3+0
- 141=1×114+27
Ex : Pour 255 et 141, on élimine tout ce qui n'est pas ni 255, ni 141, ni 3.
- 27=4×6+3
- 114=4×27+6 ×(-4) (on élimine les 6).
- 141=1×114+27 ×17 (on élimine les 27, il y en a 1 à gauche, et -16 à droite).
- 255=1×141+114 ×(-21) (on élimine les 114).
- 114=4×27+6 ×(-4) (on élimine les 6).
Exemple :
Application au calcul de la clé secrète du RSA :
Rappelons (voir cette page) la génération des clés dans le RSA. On choisit p et q deux nombres premiers, on pose n=pq, et on choisit e tel que e est premier avec le produit (p-1)(q-1) (e porte le nom d'exposant public). La clé publique est le couple (n,e). Comme e est premier avec (p-1)(q-1), il existe des entiers d et k tels que ed+k(p-1)(q-1)=1. Le couple (n,d) est la clé secrète. Le formulaire suivant permet, connaissant
p, q et e, de fabriquer la clé secrète (n,e) et la clé privée (n,d). Le calcul de d se fait en utilisant l'algorithme d'Euclide étendu.