algorithme d'Euclide étendu
L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet de calculer non seulement le PGCD de deux entiers a et b, mais également les coefficients de Bézout, c'est-à-dire les entiers relatifs u et v vérifiant l'identité au + bv = pgcd(a, b). Cette identité est garantie par le théorème de Bézout. L'algorithme d'Euclide étendu est notamment utilisé en cryptographie, en particulier pour le calcul de la clé secrète dans le protocole RSA, où il sert à déterminer l'inverse d'un entier modulo un autre entier non nul.
Sommaire
Ce que vous allez apprendre
- Suivre les divisions euclidiennes et leur point d’arrêt.
- Retrouver et contrôler un couple de coefficients de Bézout.
- Savoir quand un coefficient fournit un inverse modulaire.
- Repérer les cas où les coefficients ne sont pas uniques ou l’inverse n’existe pas.
En clair
Prenons 252 et 198. Les divisions successives de l’algorithme d’Euclide font apparaître leur plus grand diviseur commun, 18. La version étendue garde aussi la trace de la façon dont chaque reste a été obtenu.
En remontant ces calculs, elle écrit 18 comme un mélange des deux nombres de départ : quatre fois 252 moins cinq fois 198. Ces deux multiplicateurs, 4 et −5, sont des coefficients de Bézout.
Définition
L’algorithme d’Euclide étendu s’applique à deux entiers, notés a et b, qui ne sont pas tous deux nuls. Il reprend les divisions euclidiennes de l’algorithme d’Euclide et conserve, pour chaque reste, son expression comme combinaison entière de a et b.
À l’arrêt, le dernier reste non nul est le plus grand commun diviseur positif, noté PGCD. L’algorithme fournit aussi deux entiers relatifs, notés u et v, appelés coefficients de Bézout, tels que . Leur existence découle du théorème de Bézout. Le couple obtenu n’est généralement pas unique, même si le PGCD l’est.
Lorsque b est non nul et que le PGCD de a et b vaut 1, l’égalité donne immédiatement un inverse modulaire : le coefficient u est un inverse de a modulo b. Cette propriété explique l’emploi de l’algorithme en cryptographie RSA.
Le principe
Pour deux entiers a et b non simultanément nuls, on initialise deux expressions qui représentent a et b. Puis on répète les opérations suivantes :
1. On effectue la division euclidienne du plus grand reste par le plus petit.
2. On remplace les deux restes par le diviseur et le nouveau reste.
3. On applique simultanément la même soustraction aux coefficients associés.
Quand le reste devient nul, le reste précédent est le PGCD et ses deux coefficients vérifient l’identité de Bézout.
1. On effectue la division euclidienne du plus grand reste par le plus petit.
2. On remplace les deux restes par le diviseur et le nouveau reste.
3. On applique simultanément la même soustraction aux coefficients associés.
Quand le reste devient nul, le reste précédent est le PGCD et ses deux coefficients vérifient l’identité de Bézout.
Quand l'utiliser
Les données sont deux entiers, éventuellement négatifs, mais pas tous deux nuls. Les divisions peuvent être menées sur leurs valeurs absolues ; les signes des coefficients sont ensuite ajustés aux entiers de départ. Le résultat comprend le PGCD positif et au moins un couple de coefficients de Bézout.
Pour obtenir l’inverse de a modulo b, on suppose d’abord b non nul ; une condition supplémentaire est vérifiable : leur PGCD doit valoir 1. Par exemple, 6 n’a pas d’inverse modulo 15, car leur PGCD vaut 3. L’algorithme calcule encore ce PGCD et des coefficients de Bézout, mais il ne peut pas produire l’inverse demandé.
Un exemple, pas à pas
On cherche le PGCD des deux entiers 252 et 198, puis un couple de coefficients de Bézout. Les seules données de départ sont donc a = 252 et b = 198.
1. Les divisions euclidiennes successives donnent :
252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0
252 = 1 × 198 + 54
198 = 3 × 54 + 36
54 = 1 × 36 + 18
36 = 2 × 18 + 0
2. Le dernier reste non nul est 18. On remonte alors les égalités. Chaque substitution remplace un reste par l’expression fournie lors d’une division précédente :
18 = 54 − 36
18 = 54 − (198 − 3 × 54) = 4 × 54 − 198
18 = 4 × (252 − 198) − 198
18 = 54 − 36
18 = 54 − (198 − 3 × 54) = 4 × 54 − 198
18 = 4 × (252 − 198) − 198
3. Après réduction, on obtient . Ainsi, le PGCD vaut 18 et un couple de coefficients de Bézout est (4, −5). Le contrôle est direct : 4 × 252 − 5 × 198 = 1 008 − 990 = 18.
En pratique
Pour simplifier une fraction, le PGCD suffit : l’algorithme d’Euclide ordinaire est alors préférable, car les coefficients supplémentaires ne sont pas nécessaires.
Pour résoudre un calcul modulo un entier, la version étendue devient utile dès qu’un inverse est recherché. On vérifie d’abord que le nombre et le module sont premiers entre eux, puis on réduit le coefficient de Bézout modulo le module.
Dans le protocole RSA, ce calcul d’inverse modulaire intervient pour déterminer la donnée secrète associée aux paramètres publics. Si le PGCD n’est pas 1, les paramètres choisis ne conviennent pas à cette étape.
À ne pas confondre
Algorithme d’Euclide ordinaire. Il calcule le PGCD par divisions successives. La version étendue suit aussi les coefficients : pour 252 et 198, elle ne s’arrête pas au résultat 18, mais obtient également (4, −5).
Théorème de Bézout. Le théorème affirme l’existence de coefficients entiers donnant le PGCD. L’algorithme d’Euclide étendu est une procédure qui en calcule effectivement un couple pour les deux entiers fournis.
Limites et pièges
Deux zéros. Pour a = 0 et b = 0, il n’existe pas de dernier reste non nul. Cette entrée est donc exclue de la procédure décrite ; elle doit être traitée séparément selon la convention adoptée pour le PGCD.
Coefficients non uniques. Si d désigne le PGCD et si (u, v) est une solution, tout entier k fournit aussi une solution : . Il faut contrôler l’identité obtenue, sans attendre un couple unique.
Inverse modulaire absent. Des coefficients de Bézout existent même lorsque le PGCD dépasse 1, mais ils ne donnent alors pas un inverse. Avec 6 et 15, le PGCD vaut 3 : conclure que l’un des coefficients inverse 6 modulo 15 serait faux.
Pour aller plus loin
Le PGCD précise le résultat commun aux versions ordinaire et étendue de l’algorithme.
L’algorithme d’Euclide isole le mécanisme des divisions successives avant le suivi des coefficients.
L’article De Sissa à RSA prolonge l’usage cryptographique évoqué dans cette fiche.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres