12 · Bézout et algorithme d'Euclide étendu

Intuition

L'algorithme d'Euclide dit combien vaut le PGCD. L'identité de Bézout dit comment l'obtenir : elle affirme qu'on peut toujours écrire le PGCD comme une combinaison \(au + bv\) des deux nombres de départ.

Cela paraît anecdotique. C'est en réalité l'outil le plus puissant de tout le bloc arithmétique, parce qu'il donne l'inverse modulaire — c'est-à-dire la clé privée de RSA.

1. Le théorème de Bézout

Théorème de Bézout

Soient \(a, b\in\mathbb{Z}\) non tous deux nuls, et \(d = \operatorname{pgcd}(a,b)\). Alors il existe \(u, v\in\mathbb{Z}\) tels que

\[ au + bv = d \]

Exemple. \(\operatorname{pgcd}(12, 18) = 6\), et \(12\times(-1) + 18\times1 = 6\).

Le couple \((u,v)\) n'est pas unique

Si \((u,v)\) convient, alors \(\left(u + k\frac bd,\ v - k\frac ad\right)\) convient aussi pour tout \(k\in\mathbb{Z}\) — le terme ajouté est \(k\frac{ab}{d} - k\frac{ab}{d} = 0\).

Pour \((12,18)\) : \((-1,1)\) convient, mais aussi \((2,-1)\) puisque \(24-18 = 6\).

L'équation \(au+bv = c\) n'a pas toujours de solution

Elle en a si et seulement si \(d \mid c\).

Raison : \(d\) divise \(a\) et \(b\), donc divise toute combinaison \(au+bv\). Si \(d\nmid c\), aucune combinaison ne peut valoir \(c\).

Ainsi \(6u+4v = 5\) n'a aucune solution entière, car \(\operatorname{pgcd}(6,4)=2\) ne divise pas 5.

1.1 Théorème de Bézout, forme « premiers entre eux »

Caractérisation

\[ \operatorname{pgcd}(a,b) = 1 \iff \exists u,v\in\mathbb{Z},\ au+bv = 1 \]

Le sens \(\implies\) est le théorème. Le sens \(\impliedby\) est immédiat : tout diviseur commun de \(a\) et \(b\) divise \(au+bv=1\), donc vaut \(\pm1\).

C'est cette version qu'on utilise le plus, parce qu'elle est une équivalence — elle sert donc aussi bien à construire qu'à démontrer.

2. L'algorithme d'Euclide étendu

L'idée : refaire l'algorithme d'Euclide en remontant les égalités pour exprimer chaque reste en fonction de \(a\) et \(b\).

2.1 Méthode par remontée

Exemple : \(a = 240\), \(b = 46\).

Descente (Euclide classique) :

\[ 240 = 5\times46 + 10 \]

\[ 46 = 4\times10 + 6 \]

\[ 10 = 1\times6 + 4 \]

\[ 6 = 1\times4 + 2 \]

\[ 4 = 2\times2 + 0 \]

PGCD \(= 2\).

Remontée — on isole chaque reste et on substitue :

\[ 2 = 6 - 1\times4 \]

\[ = 6 - 1\times(10 - 1\times6) = 2\times6 - 1\times10 \]

\[ = 2\times(46 - 4\times10) - 10 = 2\times46 - 9\times10 \]

\[ = 2\times46 - 9\times(240 - 5\times46) = 47\times46 - 9\times240 \]

\[ \boxed{240\times(-9) + 46\times47 = 2} \]

Vérification : \(-2160 + 2162 = 2\) ✓

Ne jamais simplifier pendant la remontée

La tentation est de calculer \(2\times46 = 92\). Ne le faites pas : il faut garder \(46\) et \(240\) visibles comme facteurs, sinon on ne peut plus substituer. On ne développe qu'à la toute fin.

2.2 Méthode par tableau — plus sûre

La remontée est source d'erreurs. Le tableau la remplace avantageusement : on maintient à chaque ligne un triplet \((r, u, v)\) vérifiant l'invariant

\[ r = au + bv \]

Initialisation : \((a, 1, 0)\) et \((b, 0, 1)\). Itération : si \(r_{i-1} = q\,r_i + r_{i+1}\), alors on pose

\[ (r_{i+1},\ u_{i+1},\ v_{i+1}) = (r_{i-1},u_{i-1},v_{i-1}) - q\,(r_i,u_i,v_i) \]

Reprise de l'exemple \((240, 46)\) :

\(q\)	\(r\)	\(u\)	\(v\)	Vérification \(r = 240u+46v\)
—	240	1	0	\(240\) ✓
—	46	0	1	\(46\) ✓
5	10	1	\(-5\)	\(240-230 = 10\) ✓
4	6	\(-4\)	21	\(-960+966 = 6\) ✓
1	4	5	\(-26\)	\(1200-1196 = 4\) ✓
1	2	\(-9\)	47	\(-2160+2162 = 2\) ✓
2	0	23	\(-120\)	—

On s'arrête au dernier reste non nul : \(d = 2\), \(u = -9\), \(v = 47\).

Pourquoi le tableau est meilleur

• Vérifiable à chaque ligne : il suffit de contrôler \(r = au+bv\). Une erreur est détectée immédiatement, pas à la fin.
• Une seule passe au lieu de deux.
• Directement programmable.

3. Théorème de Gauss

Théorème de Gauss

Si \(a\mid bc\) et \(\operatorname{pgcd}(a,b) = 1\), alors \(a\mid c\).

Démonstration

Par Bézout, il existe \(u,v\) tels que \(au+bv=1\). Multiplions par \(c\) :

\[ acu + bcv = c \]

• \(a\) divise \(acu\), c'est évident ;
• \(a\) divise \(bc\) par hypothèse, donc \(a\) divise \(bcv\).

Donc \(a\) divise la somme, qui vaut \(c\). \(\blacksquare\)

L'hypothèse de coprimalité est indispensable

\(6 \mid 4\times9 = 36\), mais \(6\nmid 4\) et \(6\nmid 9\). Ici \(\operatorname{pgcd}(6,4)=2\neq1\).

Corollaire (lemme d'Euclide) : si \(p\) est premier et \(p\mid ab\), alors \(p\mid a\) ou \(p\mid b\). C'est ce lemme qui donne l'unicité de la décomposition en facteurs premiers.

Corollaire utile : si \(a\mid n\), \(b\mid n\) et \(\operatorname{pgcd}(a,b)=1\), alors \(ab\mid n\).

4. Application majeure : l'inverse modulaire

Théorème

Soit \(n\geqslant2\). L'entier \(a\) admet un inverse modulo \(n\) — c'est-à-dire un entier \(u\) tel que \(au \equiv 1 \pmod n\) — si et seulement si \(\operatorname{pgcd}(a,n)=1\).

Cet inverse est alors le coefficient \(u\) de Bézout, et il est unique modulo \(n\).

Pourquoi. \(au\equiv1\pmod n\) signifie qu'il existe \(v\) tel que \(au - 1 = -vn\), c'est-à-dire \(au + nv = 1\) : c'est exactement l'identité de Bézout.

4.1 Exemple

Trouver l'inverse de 7 modulo 26.

\(q\)	\(r\)	\(u\)	\(v\)
—	26	1	0
—	7	0	1
3	5	1	\(-3\)
1	2	\(-1\)	4
2	1	3	\(-11\)

Dernier reste non nul : \(1 = 26\times3 + 7\times(-11)\).

Donc \(7\times(-11)\equiv1\pmod{26}\), soit

\[ 7^{-1} \equiv -11 \equiv 15 \pmod{26} \]

Vérification : \(7\times15 = 105 = 4\times26+1\) ✓

Pourquoi c'est le cœur de RSA

Dans RSA, la clé publique est un exposant \(e\) premier avec \(\varphi(n) = (p-1)(q-1)\). La clé privée est

\[ d = e^{-1} \bmod \varphi(n) \]

calculée par l'algorithme d'Euclide étendu, en quelques millisecondes même pour des nombres de 2048 bits.

Un attaquant qui connaît \(e\) et \(n\) ne peut pas calculer \(d\) sans connaître \(\varphi(n)\), ce qui exigerait de factoriser \(n\). Toute la sécurité tient à cette asymétrie : Euclide étendu est facile, la factorisation ne l'est pas.

5. Équations diophantiennes \(ax+by=c\)

Méthode complète

1. Calculer \(d = \operatorname{pgcd}(a,b)\).
2. Si \(d\nmid c\) : aucune solution. On s'arrête.
3. Sinon, trouver \((u_0,v_0)\) par Euclide étendu tel que \(au_0+bv_0 = d\).
4. Multiplier par \(\frac cd\) : une solution particulière est \(\left(u_0\frac cd,\ v_0\frac cd\right)\).
5. Solution générale : \(\displaystyle x = x_0 + k\frac bd, \qquad y = y_0 - k\frac ad, \qquad k\in\mathbb{Z}\)

Exemple. Résoudre \(15x + 21y = 12\) dans \(\mathbb{Z}^2\).

\(d = \operatorname{pgcd}(15,21) = 3\), et \(3\mid 12\) ✓

Bézout : \(15\times3 - 21\times2 = 45-42 = 3\), donc \((u_0,v_0)=(3,-2)\).

En multipliant par \(\frac{12}{3}=4\) : \((x_0,y_0) = (12,-8)\).

Vérification : \(180 - 168 = 12\) ✓

Solution générale :

\[ x = 12 + 7k, \qquad y = -8 - 5k, \qquad k\in\mathbb{Z} \]

Vérification pour \(k=1\) : \(15(19)+21(-13) = 285-273 = 12\) ✓

Exemples traités

Exemple 1 — Euclide étendu par tableau

Trouver \(u,v\) tels que \(161u + 28v = \operatorname{pgcd}(161,28)\).

\(q\)	\(r\)	\(u\)	\(v\)	Contrôle \(161u+28v\)
—	161	1	0	161 ✓
—	28	0	1	28 ✓
5	21	1	\(-5\)	\(161-140=21\) ✓
1	7	\(-1\)	6	\(-161+168=7\) ✓
3	0	4	\(-23\)	—

\(\operatorname{pgcd}(161,28) = 7\) et

\[ 161\times(-1) + 28\times6 = 7 \]

Exemple 2 — Inverse modulaire

Calculer \(17^{-1}\bmod 43\).

\(q\)	\(r\)	\(u\)	\(v\)
—	43	1	0
—	17	0	1
2	9	1	\(-2\)
1	8	\(-1\)	3
1	1	2	\(-5\)

\(43\times2 + 17\times(-5) = 86-85 = 1\) ✓

\[ 17^{-1}\equiv -5 \equiv 38 \pmod{43} \]

Vérification : \(17\times38 = 646 = 15\times43+1\) ✓

Exemple 3 — Une démonstration par Bézout

Montrer que si \(\operatorname{pgcd}(a,b)=1\) et \(\operatorname{pgcd}(a,c)=1\), alors \(\operatorname{pgcd}(a,bc)=1\).

Par Bézout, il existe \(u,v,s,t\) tels que

\[ au+bv = 1 \qquad\text{et}\qquad as+ct = 1 \]

Multiplions les deux égalités :

\[ (au+bv)(as+ct) = 1 \]

\[ a^2us + auct + bvas + bcvt = 1 \]

\[ a\underbrace{(aus + uct + bvs)}_{U} + bc\underbrace{(vt)}_{V} = 1 \]

On a exhibé une combinaison de \(a\) et \(bc\) égale à 1 : par la caractérisation de Bézout, \(\operatorname{pgcd}(a,bc)=1\). \(\blacksquare\)

La technique

Pour démontrer une coprimalité, exhiber une relation de Bézout. C'est beaucoup plus efficace que de raisonner sur les facteurs premiers, et cela fonctionne même quand on ne sait pas factoriser.

Erreurs fréquentes

Erreur	Correction
Résoudre \(ax+by=c\) sans vérifier \(d\mid c\)	Peut n'avoir aucune solution
Simplifier pendant la remontée	Garder \(a\) et \(b\) comme facteurs
Croire \((u,v)\) unique	Infinité de solutions
Oublier de multiplier par \(c/d\)	Solution particulière fausse
Signe du terme en \(k\)	\(x\) gagne \(+\frac bd\), \(y\) perd \(\frac ad\)
Inverse modulaire négatif laissé tel quel	Le ramener dans \([0;n[\)

Exercices

★ Exercice 1. Par l'algorithme d'Euclide étendu, trouver \(u,v\) tels que \(au+bv = \operatorname{pgcd}(a,b)\).

a) \(a=17\), \(b=5\) b) \(a=48\), \(b=18\) c) \(a=101\), \(b=37\)

★★ Exercice 2. Calculer les inverses modulaires.

a) \(5^{-1} \bmod 12\) b) \(11^{-1}\bmod 30\) c) \(9^{-1}\bmod 26\) d) \(6^{-1}\bmod 15\) — que se passe-t-il ?

★★ Exercice 3. Résoudre dans \(\mathbb{Z}^2\).

a) \(7x+11y = 1\) b) \(6x+9y = 15\) c) \(4x+6y = 7\)

★★ Exercice 4. Un distributeur ne dispose que de pièces de 7 € et de 11 €. Peut-on payer exactement 100 € ? Donner toutes les façons de le faire avec des nombres positifs de pièces.

★★★ Exercice 5. Soient \(a,b\) premiers entre eux.

a) Montrer que \(\operatorname{pgcd}(a+b, ab) = 1\). b) Montrer que \(\operatorname{pgcd}(a+b, a-b)\) vaut 1 ou 2, et préciser dans quels cas.

★★★ Exercice 6. Montrer que pour tout \(n\in\mathbb{N}\), la fraction

\[ \frac{21n+4}{14n+3} \]

est irréductible.

C'est le problème 1 des Olympiades internationales de 1959.

★★★ Exercice 7. Soit \(p\) un nombre premier.

a) Montrer que tout \(a\in\{1,\dots,p-1\}\) admet un inverse modulo \(p\). b) En déduire que \(\mathbb{Z}/p\mathbb{Z}\) privé de 0 est un groupe pour la multiplication. c) Montrer que \(a^2\equiv1\pmod p\) implique \(a\equiv\pm1\pmod p\). d) En déduire le théorème de Wilson : \((p-1)! \equiv -1 \pmod p\). Indication : dans le produit \((p-1)!\), appariez chaque élément avec son inverse.

★★★★ Exercice 8. On considère le chiffrement affine : une lettre de rang \(x\in\{0,\dots,25\}\) est chiffrée en

\[ y = (ax+b) \bmod 26 \]

a) À quelle condition sur \(a\) le chiffrement est-il déchiffrable ? b) Combien de clés \((a,b)\) valides existe-t-il ? c) Donner la formule de déchiffrement. d) Déchiffrer le message IHHW sachant que la clé est \(a=7\), \(b=3\).

★★★★ Exercice 9 — lien informatique. Implémentation de RSA en petit.

On prend \(p=11\), \(q=13\), donc \(n = 143\) et \(\varphi(n) = 10\times12 = 120\).

a) Vérifier que \(e=7\) est un exposant valide. b) Calculer la clé privée \(d = e^{-1}\bmod 120\) par Euclide étendu. c) Chiffrer le message \(m = 9\) : calculer \(c = m^e \bmod n\) par exponentiation rapide. d) Déchiffrer : vérifier que \(c^d \bmod n = m\). e) Expliquer pourquoi un attaquant connaissant \((n,e) = (143,7)\) peut retrouver \(d\) ici, et pourquoi il ne le peut pas quand \(n\) fait 2048 bits.

★★★★ Exercice 10. Écrire l'algorithme d'Euclide étendu en Python et le tester.

a) Version itérative avec le tableau. b) Vérifier l'invariant \(r = au+bv\) à chaque étape par une assertion. c) En déduire une fonction inverse_modulaire(a, n) qui lève une exception si l'inverse n'existe pas.

---

Corrigés

Corrigé — Exercice 1

a) \(17 = 3\times5+2\) ; \(5 = 2\times2+1\) ; \(2 = 2\times1+0\).

\(q\)	\(r\)	\(u\)	\(v\)
—	17	1	0
—	5	0	1
3	2	1	\(-3\)
2	1	\(-2\)	7

\(17\times(-2)+5\times7 = -34+35 = 1\) ✓

b) \(\operatorname{pgcd}(48,18)=6\).

\(q\)	\(r\)	\(u\)	\(v\)
—	48	1	0
—	18	0	1
2	12	1	\(-2\)
1	6	\(-1\)	3

\(48\times(-1)+18\times3 = -48+54 = 6\) ✓

c) \(101 = 2\times37+27\) ; \(37=1\times27+10\) ; \(27=2\times10+7\) ; \(10=1\times7+3\) ; \(7=2\times3+1\).

\(q\)	\(r\)	\(u\)	\(v\)
—	101	1	0
—	37	0	1
2	27	1	\(-2\)
1	10	\(-1\)	3
2	7	3	\(-8\)
1	3	\(-4\)	11
2	1	11	\(-30\)

\(101\times11 + 37\times(-30) = 1111-1110 = 1\) ✓

Corrigé — Exercice 2

a) \(\operatorname{pgcd}(5,12)=1\). \(5\times5 = 25 = 2\times12+1\), donc

\[ 5^{-1}\equiv 5 \pmod{12} \]

(5 est son propre inverse.)

b) \(\operatorname{pgcd}(11,30)=1\). \(11\times11 = 121 = 4\times30+1\), donc

\[ 11^{-1}\equiv 11\pmod{30} \]

c) \(\operatorname{pgcd}(9,26)=1\). Euclide étendu : \(26 = 2\times9+8\) ; \(9 = 1\times8+1\).

\(1 = 9-8 = 9-(26-2\times9) = 3\times9 - 26\).

\[ 9^{-1}\equiv 3\pmod{26} \]

Vérification : \(27 = 26+1\) ✓

d) \(\operatorname{pgcd}(6,15) = 3 \neq 1\) : l'inverse n'existe pas.

En effet, \(6u \bmod 15\) ne prend que les valeurs multiples de 3 : \(0, 6, 12, 3, 9\). La valeur 1 n'est jamais atteinte.

Corrigé — Exercice 3

a) \(\operatorname{pgcd}(7,11)=1\), qui divise 1 ✓

Bézout : \(7\times(-3)+11\times2 = -21+22 = 1\). Solution particulière \((-3,2)\).

\[ x = -3+11k,\qquad y = 2-7k,\qquad k\in\mathbb{Z} \]

Vérification \(k=1\) : \(7(8)+11(-5) = 56-55 = 1\) ✓

b) \(\operatorname{pgcd}(6,9)=3\), et \(3\mid15\) ✓

Bézout pour le PGCD : \(6\times(-1)+9\times1 = 3\). On multiplie par \(\frac{15}{3}=5\) : \((x_0,y_0) = (-5,5)\).

\[ x = -5+3k,\qquad y = 5-2k,\qquad k\in\mathbb{Z} \]

Vérification \(k=2\) : \(6(1)+9(1) = 15\) ✓

c) \(\operatorname{pgcd}(4,6)=2\), et \(2\nmid7\). Aucune solution.

(Le membre de gauche est toujours pair, le droit est impair.)

Corrigé — Exercice 4

On résout \(7x+11y = 100\) avec \(x,y\geqslant0\).

\(\operatorname{pgcd}(7,11)=1\) divise 100 ✓

D'après l'exercice 3a, \(7\times(-3)+11\times2 = 1\). En multipliant par 100 : \((x_0,y_0) = (-300, 200)\).

Solution générale :

\[ x = -300+11k,\qquad y = 200-7k \]

Contraintes de positivité :

\[ -300+11k \geqslant 0 \implies k \geqslant \frac{300}{11} \approx 27{,}27 \implies k\geqslant28 \]

\[ 200-7k\geqslant0 \implies k \leqslant \frac{200}{7}\approx 28{,}57 \implies k\leqslant28 \]

Une seule valeur : \(k = 28\).

\[ x = -300+308 = 8, \qquad y = 200-196 = 4 \]

Vérification : \(7\times8 + 11\times4 = 56+44 = 100\) ✓

Il y a exactement une façon de payer 100 € : 8 pièces de 7 € et 4 pièces de 11 €.

Le problème de Frobenius

Avec des pièces de 7 et 11, le plus grand montant impossible à payer est \(7\times11-7-11 = 55\). Au-delà, tout montant est réalisable. C'est la formule de Sylvester, valable pour deux dénominations premières entre elles.

Corrigé — Exercice 5

a) Par Bézout, il existe \(u,v\) avec \(au+bv=1\).

Soit \(d\) un diviseur commun de \(a+b\) et \(ab\). Montrons \(d = \pm1\).

Approche plus directe : montrons d'abord \(\operatorname{pgcd}(a+b, a) = \operatorname{pgcd}(b,a) = 1\) (lemme d'Euclide), et de même \(\operatorname{pgcd}(a+b,b)=1\).

Donc \(a+b\) est premier avec \(a\) et avec \(b\). Par le résultat de l'exemple 3, \(a+b\) est premier avec le produit \(ab\). \(\blacksquare\)

b) Soit \(d = \operatorname{pgcd}(a+b, a-b)\).

\(d\) divise la somme \(2a\) et la différence \(2b\). Donc \(d\) divise \(\operatorname{pgcd}(2a,2b) = 2\operatorname{pgcd}(a,b) = 2\).

Donc \(d\in\{1,2\}\).

• Si \(a\) et \(b\) sont de parités différentes : \(a+b\) est impair, donc \(d\) est impair, donc \(d=1\).
• Si \(a\) et \(b\) sont tous deux impairs (ils ne peuvent être tous deux pairs, étant premiers entre eux) : \(a+b\) et \(a-b\) sont tous deux pairs, donc \(d=2\).

\(\blacksquare\)

Corrigé — Exercice 6

Une fraction est irréductible si numérateur et dénominateur sont premiers entre eux. Cherchons une relation de Bézout.

\[ 3\times(14n+3) - 2\times(21n+4) = 42n+9-42n-8 = 1 \]

On a donc exhibé une combinaison entière des deux qui vaut 1. Par la caractérisation de Bézout,

\[ \operatorname{pgcd}(21n+4,\ 14n+3) = 1 \]

pour tout \(n\). La fraction est toujours irréductible. \(\blacksquare\)

Comment trouver les coefficients

On applique Euclide au niveau des expressions : \(21n+4 = 1\times(14n+3) + (7n+1)\), puis \(14n+3 = 2\times(7n+1)+1\). On remonte : \(1 = (14n+3) - 2(7n+1) = (14n+3) - 2[(21n+4)-(14n+3)] = 3(14n+3) - 2(21n+4)\) ✓

L'algorithme d'Euclide fonctionne sur les polynômes en \(n\), ce qui donne la relation valable pour tous les \(n\) d'un coup.

Corrigé — Exercice 7

a) Soit \(a\in\{1,\dots,p-1\}\). Comme \(p\) est premier et \(0 < a < p\), le seul diviseur commun possible de \(a\) et \(p\) est 1 (les diviseurs de \(p\) sont 1 et \(p\), et \(p\nmid a\)). Donc \(\operatorname{pgcd}(a,p)=1\) et l'inverse existe. \(\blacksquare\)

b) La multiplication modulo \(p\) est associative, admet 1 pour neutre, et tout élément non nul a un inverse par a). Reste la stabilité : si \(a,b\not\equiv0\), alors \(ab\not\equiv0\) — sinon \(p\mid ab\) et le lemme d'Euclide donnerait \(p\mid a\) ou \(p\mid b\). C'est bien un groupe.

c) \(a^2\equiv1\) signifie \(p \mid a^2-1 = (a-1)(a+1)\). Par le lemme d'Euclide, \(p\mid a-1\) ou \(p\mid a+1\), soit \(a\equiv1\) ou \(a\equiv-1\). \(\blacksquare\)

d) Dans le produit \((p-1)! = 1\times2\times\dots\times(p-1)\), apparions chaque élément avec son inverse modulo \(p\).

D'après c), les seuls éléments égaux à leur propre inverse sont \(1\) et \(p-1 \equiv -1\). Tous les autres se regroupent en paires \(\{a, a^{-1}\}\) de produit \(\equiv 1\).

Il reste donc

\[ (p-1)! \equiv 1 \times (-1) \times \underbrace{1\times1\times\dots\times1}_{\text{paires}} \equiv -1 \pmod p \]

\(\blacksquare\)

Vérification \(p=7\) : \(6! = 720 = 102\times7+6\), et \(6\equiv-1\pmod7\) ✓

Corrigé — Exercice 8

a) Le chiffrement est déchiffrable si la fonction \(x\mapsto ax+b\) est bijective sur \(\mathbb{Z}/26\mathbb{Z}\), ce qui exige que \(a\) soit inversible modulo 26, c'est-à-dire

\[ \operatorname{pgcd}(a,26)=1 \]

b) \(26 = 2\times13\). Les \(a\) valides sont ceux qui ne sont ni pairs ni multiples de 13. Leur nombre est

\[ \varphi(26) = \varphi(2)\varphi(13) = 1\times12 = 12 \]

Ce sont \(\{1,3,5,7,9,11,15,17,19,21,23,25\}\).

Avec 26 valeurs possibles pour \(b\) : \(12\times26 = 312\) clés.

C'est dérisoire — une recherche exhaustive est immédiate. Le chiffrement affine n'offre aucune sécurité.

c) \(y = ax+b\) donne \(x = a^{-1}(y-b)\bmod 26\).

d) Ici \(a=7\), \(b=3\). On a calculé \(7^{-1}\equiv15\pmod{26}\) dans la leçon.

IHHW correspond aux rangs \(8, 7, 7, 22\) (avec A=0).

\(y\)	\(y-3\)	\(15(y-3)\)	mod 26	Lettre
8	5	75	75−52=23	X
7	4	60	60−52=8	I
7	4	60	8	I
22	19	285	285−260=25	Z

Hmm, cela donne XIIZ. Vérifions dans l'autre sens : chiffrons THIS…

Reprenons : chiffrons X (rang 23) : \(7\times23+3 = 164 = 6\times26+8\), soit rang 8 = I ✓ Le déchiffrement est cohérent.

Message déchiffré : XIIZ.

(Le message clair n'est pas un mot français — l'exercice teste la mécanique, pas la cryptanalyse.)

Corrigé — Exercice 9

a) \(e=7\) est valide si \(\operatorname{pgcd}(7,120)=1\). \(120 = 17\times7+1\), donc le PGCD vaut 1 ✓

b) Euclide étendu sur \((120, 7)\) :

\(q\)	\(r\)	\(u\)	\(v\)
—	120	1	0
—	7	0	1
17	1	1	\(-17\)

\(120\times1 + 7\times(-17) = 120-119 = 1\) ✓

\[ d \equiv -17 \equiv 103 \pmod{120} \]

Vérification : \(7\times103 = 721 = 6\times120+1\) ✓

c) \(c = 9^7 \bmod 143\), par exponentiation rapide :

• \(9^1 = 9\)
• \(9^2 = 81\)
• \(9^4 = 81^2 = 6561\). Or \(6561 = 45\times143 + 126\), donc \(9^4 \equiv 126 \equiv -17 \pmod{143}\).

\[ 9^7 = 9^4\cdot9^2\cdot9^1 \equiv (-17)\times81\times9 \pmod{143} \]

\((-17)\times81 = -1377\). Or \(1377 = 9\times143+90\), donc \(-1377 \equiv -90 \equiv 53 \pmod{143}\).

\(53\times9 = 477 = 3\times143+48\).

\[ c = 48 \]

d) Il faut calculer \(48^{103}\bmod143\). Décomposons \(103 = 64+32+4+2+1\) en binaire (1100111).

\(k\)	\(48^{2^k}\bmod143\)
0	48
1	\(48^2 = 2304 = 16\times143+16 \to 16\)
2	\(16^2=256 = 143+113 \to 113\)
3	\(113^2 = 12769 = 89\times143+42 \to 42\)
4	\(42^2 = 1764 = 12\times143+48 \to 48\)
5	\(48^2 \to 16\)
6	\(16^2 \to 113\)

\[ 48^{103} \equiv 48^{64}\cdot48^{32}\cdot48^{4}\cdot48^{2}\cdot48^{1} \equiv 113\times16\times113\times16\times48 \pmod{143} \]

\(113\times16 = 1808 = 12\times143 + 92 \to 92\). \(92\times113 = 10396 = 72\times143+100 \to 100\). \(100\times16 = 1600 = 11\times143+27 \to 27\). \(27\times48 = 1296 = 9\times143+9 \to 9\).

\[ 48^{103} \equiv 9 = m \quad\checkmark \]

e) Ici, \(n = 143\) se factorise instantanément en \(11\times13\). Un attaquant calcule alors \(\varphi(143) = 120\) et applique Euclide étendu exactement comme nous : il obtient \(d = 103\) en quelques microsecondes.

Avec \(n\) de 2048 bits (environ 617 chiffres décimaux), la factorisation est hors de portée : le meilleur algorithme connu, le crible général de corps de nombres, demanderait de l'ordre de \(10^{34}\) opérations. Aucun record public ne dépasse 829 bits (RSA-250, factorisé en 2020 avec 2700 années-cœur de calcul).

L'asymétrie est là et nulle part ailleurs : Euclide étendu est en \(O(\log n)\), la factorisation est sous-exponentielle mais surpolynomiale.

Corrigé — Exercice 10

a) et b)

def euclide_etendu(a, b):
    """Renvoie (d, u, v) avec d = pgcd(a,b) et a*u + b*v = d."""
    r0, u0, v0 = a, 1, 0
    r1, u1, v1 = b, 0, 1
    while r1 != 0:
        assert r0 == a * u0 + b * v0      # invariant
        assert r1 == a * u1 + b * v1
        q = r0 // r1
        r0, u0, v0, r1, u1, v1 = (
            r1, u1, v1,
            r0 - q * r1, u0 - q * u1, v0 - q * v1,
        )
    return r0, u0, v0


def inverse_modulaire(a, n):
    """Inverse de a modulo n, ou ValueError s'il n'existe pas."""
    d, u, _ = euclide_etendu(a, n)
    if d != 1:
        raise ValueError(f"{a} n'est pas inversible modulo {n} (pgcd={d})")
    return u % n


# --- vérifications ---
d, u, v = euclide_etendu(240, 46)
assert (d, 240 * u + 46 * v) == (2, 2)

assert inverse_modulaire(7, 26) == 15
assert (7 * 15) % 26 == 1
assert inverse_modulaire(17, 43) == 38
assert inverse_modulaire(7, 120) == 103

try:
    inverse_modulaire(6, 15)
except ValueError:
    pass
else:
    raise AssertionError("6 ne devrait pas être inversible mod 15")

print("OK")

c) La fonction inverse_modulaire ci-dessus lève une ValueError quand \(\operatorname{pgcd}(a,n)\neq1\), et ramène le résultat dans \([0;n[\) grâce à u % n — qui, en Python, renvoie bien un reste positif (voir l'avertissement du chapitre 11 sur % en C et en Java).

Pour aller plus loin

Python fournit depuis la version 3.8 pow(a, -1, n), qui calcule directement l'inverse modulaire. La version manuelle reste utile pour comprendre — et parce que euclide_etendu donne en plus les coefficients \(u\) et \(v\), dont on a besoin pour le théorème des restes chinois au chapitre suivant.

---

Chapitre suivant : Congruences et théorème des restes chinois.