13 · Congruences et théorème des restes chinois¶
Intuition
Une congruence, c'est une égalité « à un multiple près ». Dire qu'il est 15 h ou 3 h de l'après-midi, c'est la même chose modulo 12 : on a décidé d'ignorer les multiples de 12.
Cette idée simple — ne retenir que le reste — transforme des problèmes infinis en problèmes finis. Au lieu de raisonner sur \(\mathbb{Z}\), on raisonne sur \(n\) classes. C'est le mécanisme de tous les algorithmes de hachage, de toute la cryptographie asymétrique, et de la vérification par clé de contrôle.
1. Congruences¶
Définition
Soient \(a,b\in\mathbb{Z}\) et \(n\geqslant1\). On dit que \(a\) est congru à \(b\) modulo \(n\), noté
si \(n \mid (a-b)\), c'est-à-dire si \(a\) et \(b\) ont le même reste dans la division euclidienne par \(n\).
Exemples. \(17\equiv5\pmod{12}\), car \(17-5 = 12\). \(-3\equiv4\pmod7\), car \(-3-4 = -7\).
1.1 Règles de calcul¶
Compatibilité avec les opérations
Si \(a\equiv b\) et \(c\equiv d\) (modulo \(n\)), alors
Conséquence pratique : dans un calcul modulo \(n\), on peut réduire à chaque étape. C'est ce qui permet de calculer \(7^{100}\bmod13\) sans jamais manipuler un nombre de 85 chiffres.
La division n'est PAS compatible
\(6\equiv0\pmod6\) et \(3\equiv3\pmod 6\), mais on ne peut pas « simplifier par 3 » : \(2 \not\equiv 0 \pmod 6\).
La règle correcte :
Sans la coprimalité, la simplification est fausse. C'est l'erreur la plus fréquente du chapitre.
Plus généralement, si \(d = \operatorname{pgcd}(c,n)\) : \(ac\equiv bc\pmod n \iff a\equiv b \pmod{n/d}\).
1.2 L'anneau \(\mathbb{Z}/n\mathbb{Z}\)¶
L'ensemble des classes de congruence modulo \(n\) se note \(\mathbb{Z}/n\mathbb{Z}\) ; il compte exactement \(n\) éléments, \(\bar0, \bar1,\dots,\overline{n-1}\).
Éléments inversibles
\(\bar a\) est inversible dans \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(\operatorname{pgcd}(a,n)=1\) (chapitre 12).
Leur nombre est l'indicatrice d'Euler \(\varphi(n)\).
Calcul de \(\varphi\) : si \(n = p_1^{\alpha_1}\cdots p_k^{\alpha_k}\), alors
Cas particuliers utiles :
- \(\varphi(p) = p-1\) pour \(p\) premier ;
- \(\varphi(pq) = (p-1)(q-1)\) pour \(p\neq q\) premiers — c'est la formule utilisée dans RSA ;
- \(\varphi(p^k) = p^k - p^{k-1}\).
Exemple. \(\varphi(36) = \varphi(2^2\cdot3^2) = 36\left(1-\frac12\right)\left(1-\frac13\right) = 36\times\frac12\times\frac23 = 12\).
2. Deux théorèmes fondamentaux¶
Petit théorème de Fermat
Si \(p\) est premier et \(p\nmid a\), alors
Sous forme sans condition : \(a^p \equiv a \pmod p\) pour tout \(a\).
Théorème d'Euler
Si \(\operatorname{pgcd}(a,n)=1\), alors
Le petit théorème de Fermat en est le cas particulier \(n = p\).
Utilisation typique : réduire un exposant énorme.
Comme \(13\) est premier et \(13\nmid7\), on a \(7^{12}\equiv1\). Or \(100 = 8\times12+4\), donc
\(7^2 = 49 \equiv 10 \equiv -3\), donc \(7^4\equiv9\pmod{13}\).
3. Le théorème des restes chinois¶
Théorème (CRT)
Soient \(n_1,\dots,n_k\) deux à deux premiers entre eux, et \(N = n_1n_2\cdots n_k\). Alors le système
admet une solution unique modulo \(N\).
L'hypothèse de coprimalité deux à deux est indispensable
Le système
n'a aucune solution : la première congruence impose \(x\) impair, la seconde impose \(x\) pair. Ici \(\operatorname{pgcd}(4,6)=2\neq1\).
Deux à deux, pas seulement globalement : \(n_1=6\), \(n_2=10\), \(n_3=15\) ont un PGCD global de 1, mais ne sont pas deux à deux premiers entre eux.
3.1 Méthode de résolution constructive¶
Algorithme
Pour chaque \(i\) :
- poser \(N_i = \dfrac{N}{n_i}\) (produit de tous les autres modules) ;
- calculer \(M_i = N_i^{-1} \bmod n_i\) par Euclide étendu — il existe car \(\operatorname{pgcd}(N_i, n_i)=1\) ;
- la solution est \(\displaystyle x \equiv \sum_{i=1}^{k} a_i\,N_i\,M_i \pmod N\)
Pourquoi ça marche : modulo \(n_j\), tous les termes de la somme sauf le \(j\)-ième sont nuls (car \(n_j \mid N_i\) pour \(i\neq j\)), et le terme restant vaut \(a_j N_j M_j \equiv a_j \times 1 = a_j\).
3.2 Exemple détaillé¶
Les modules \(3, 5, 7\) sont deux à deux premiers entre eux. \(N = 105\).
| \(i\) | \(n_i\) | \(a_i\) | \(N_i = N/n_i\) | \(N_i \bmod n_i\) | \(M_i = N_i^{-1}\) |
|---|---|---|---|---|---|
| 1 | 3 | 2 | 35 | \(35\equiv2\) | \(2^{-1}\equiv 2\) (car \(4\equiv1\)) |
| 2 | 5 | 3 | 21 | \(21\equiv1\) | \(1\) |
| 3 | 7 | 2 | 15 | \(15\equiv1\) | \(1\) |
\(233 = 2\times105 + 23\), donc
Vérification : \(23 = 7\times3+2\) ✓ ; \(23 = 4\times5+3\) ✓ ; \(23 = 3\times7+2\) ✓
3.3 Méthode par substitutions successives¶
Plus rapide pour deux ou trois congruences, et moins mécanique.
De \(x\equiv2\pmod3\), on écrit \(x = 3t+2\).
En reportant dans la deuxième : \(3t+2\equiv3\pmod5\), soit \(3t\equiv1\pmod5\). Comme \(3^{-1}\equiv2\pmod5\) (car \(6\equiv1\)), on obtient \(t\equiv2\pmod5\), soit \(t = 5s+2\).
Donc \(x = 3(5s+2)+2 = 15s+8\).
En reportant dans la troisième : \(15s+8\equiv2\pmod7\), soit \(s+1\equiv2\), soit \(s\equiv1\pmod7\), soit \(s = 7r+1\).
Même résultat ✓
4. Applications¶
4.1 Critères de divisibilité¶
Les règles apprises à l'école sont des congruences déguisées.
Comme \(10\equiv1\pmod9\), on a \(10^k\equiv1\) pour tout \(k\), donc un nombre est congru à la somme de ses chiffres modulo 9. D'où le critère de divisibilité par 9, et par 3.
Comme \(10\equiv-1\pmod{11}\), on a \(10^k\equiv(-1)^k\) : un nombre est congru à la somme alternée de ses chiffres modulo 11.
4.2 Clés de contrôle¶
Le numéro de sécurité sociale français comporte une clé de contrôle de deux chiffres, égale à \(97 - (\text{numéro} \bmod 97)\). Une erreur de saisie sur un chiffre modifie le reste, donc invalide la clé.
L'IBAN utilise un contrôle modulo 97 : le numéro réarrangé doit être \(\equiv1\pmod{97}\).
Pourquoi 97
C'est un nombre premier proche de 100. Sa primalité garantit qu'aucun facteur commun ne peut « masquer » une erreur, et sa taille assure qu'une erreur aléatoire n'est pas détectée avec probabilité seulement \(1/97 \approx 1\%\).
4.3 RSA — la boucle est bouclée¶
Le protocole complet
Génération des clés.
- Choisir deux grands premiers \(p\) et \(q\), poser \(n = pq\).
- Calculer \(\varphi(n) = (p-1)(q-1)\).
- Choisir \(e\) premier avec \(\varphi(n)\) — la clé publique est \((n,e)\).
- Calculer \(d = e^{-1}\bmod\varphi(n)\) par Euclide étendu — la clé privée est \(d\).
Chiffrement : \(c = m^e\bmod n\). Déchiffrement : \(m = c^d\bmod n\).
Pourquoi le déchiffrement redonne le message
Par construction, \(ed\equiv1\pmod{\varphi(n)}\), donc \(ed = 1+k\varphi(n)\) pour un entier \(k\).
Si \(\operatorname{pgcd}(m,n)=1\), le théorème d'Euler donne \(m^{\varphi(n)}\equiv1\), d'où \(c^d\equiv m\pmod n\). \(\blacksquare\)
(Le cas \(\operatorname{pgcd}(m,n)\neq1\) se traite séparément par le CRT, et le résultat reste vrai.)
Où le CRT accélère RSA
Le déchiffrement \(c^d\bmod n\) avec \(n\) de 2048 bits est coûteux. On calcule plutôt
puis on recombine par le CRT. Les exposants et les modules font 1024 bits au lieu de 2048 : le coût, en \(O(k^3)\), est divisé par \(2^3 = 8\) pour chacun des deux calculs, soit un gain global d'un facteur 4.
C'est ce que fait toute implémentation sérieuse — d'où le fait que les fichiers de clé privée RSA stockent \(p\), \(q\), \(d\bmod(p-1)\) et \(d\bmod(q-1)\), et pas seulement \(d\).
Exemples traités¶
Exemple 1 — Exponentiation modulaire
Calculer \(3^{2026}\bmod 11\).
11 est premier, \(11\nmid3\), donc \(3^{10}\equiv1\pmod{11}\) (Fermat).
\(2026 = 202\times10 + 6\), donc
\(3^2 = 9\), \(3^4 = 81 \equiv 4\), \(3^6 = 3^4\cdot3^2 \equiv 4\times9 = 36 \equiv 3\pmod{11}\).
Exemple 2 — Le problème historique
« Une bande de 17 pirates possède un trésor d'or. Ils veulent le partager également ; il reste 3 pièces. Ils se battent, un pirate meurt. Le partage entre 16 laisse 10 pièces. Nouvelle bagarre, nouveau mort : le partage entre 15 tombe juste. Quel est le nombre minimal de pièces ? »
Les modules 17, 16, 15 sont deux à deux premiers entre eux ✓ \(N = 17\times16\times15 = 4080\).
Par substitution : \(x = 15u\). La deuxième congruence donne \(15u\equiv10\pmod{16}\), soit \(-u\equiv10\), soit \(u\equiv-10\equiv6\pmod{16}\). Donc \(u = 16v+6\) et \(x = 240v+90\).
La troisième : \(240v+90\equiv3\pmod{17}\). Or \(240 = 14\times17+2\), donc \(240\equiv2\) ; et \(90 = 5\times17+5\), donc \(90\equiv5\). D'où
(on a simplifié par 2, licite car \(\operatorname{pgcd}(2,17)=1\)).
\(v = 17w+16\), donc \(x = 240(17w+16)+90 = 4080w + 3930\).
Nombre minimal : 3930 pièces.
Vérification : \(3930 = 231\times17+3\) ✓ ; \(3930 = 245\times16+10\) ✓ ; \(3930 = 262\times15\) ✓
Exemple 3 — Chiffre des unités
Quel est le dernier chiffre de \(7^{2026}\) ?
Il s'agit de \(7^{2026}\bmod10\). Or \(\varphi(10) = 4\) et \(\operatorname{pgcd}(7,10)=1\), donc \(7^4\equiv1\pmod{10}\).
\(2026 = 506\times4+2\), donc
Le dernier chiffre est 9.
On peut le vérifier sur le cycle : \(7, 9, 3, 1, 7, 9, 3, 1,\dots\) de période 4. Le rang \(2026 \equiv 2 \pmod 4\) donne bien le deuxième terme, 9.
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| Simplifier \(ac\equiv bc\) par \(c\) | Exige \(\operatorname{pgcd}(c,n)=1\) |
| Appliquer le CRT à des modules non coprimes | Peut n'avoir aucune solution |
| Réduire l'exposant modulo \(n\) | Il se réduit modulo \(\varphi(n)\) |
| Utiliser Fermat quand \(p\mid a\) | L'hypothèse \(p\nmid a\) est requise |
| \(\varphi(pq) = pq-1\) | C'est \((p-1)(q-1)\) |
| Oublier de ramener le résultat dans \([0;n[\) | Convention de présentation |
Exercices¶
★ Exercice 1. Calculer.
a) \(17^2 \bmod 5\) b) \((-23)\bmod 7\) c) \(2^{10}\bmod 11\) d) \(123456 \bmod 9\)
★ Exercice 2. Résoudre.
a) \(3x\equiv1\pmod7\) b) \(4x\equiv2\pmod6\) c) \(5x\equiv3\pmod{10}\)
★★ Exercice 3. Calculer \(\varphi(n)\) pour \(n = 12\), \(35\), \(100\), \(101\), \(1001\).
★★ Exercice 4. Utiliser le petit théorème de Fermat pour calculer :
a) \(5^{100}\bmod7\) b) \(2^{1000}\bmod13\) c) \(3^{2026}\bmod 17\)
★★ Exercice 5. Résoudre par le théorème des restes chinois.
★★★ Exercice 6. Démontrer les critères de divisibilité par 3, par 9 et par 11 à l'aide des congruences.
Puis démontrer le critère par 7 suivant : on retranche le double du chiffre des unités au nombre formé par les chiffres restants, et l'on recommence. Exemple : \(364 \to 36 - 8 = 28\), divisible par 7.
★★★ Exercice 7. Montrer que pour tout \(n\in\mathbb{N}\) :
a) \(n^5 \equiv n \pmod{30}\) b) \(n^7\equiv n\pmod{42}\)
Indication : \(30 = 2\times3\times5\) et \(42 = 2\times3\times7\). Traitez chaque facteur premier par Fermat.
★★★ Exercice 8. Un entier \(x\) vérifie \(x\equiv 2\pmod 5\) et \(x\equiv 3\pmod 7\).
a) Trouver tous les \(x\) possibles. b) Combien y en a-t-il entre 1 et 1000 ?
★★★★ Exercice 9. Le test de Fermat de primalité consiste à tirer \(a\) au hasard et vérifier \(a^{n-1}\equiv1\pmod n\).
a) Justifier que si le test échoue, \(n\) n'est certainement pas premier. b) Vérifier que \(n = 561 = 3\times11\times17\) passe le test pour tout \(a\) premier avec 561. Indication : montrez que \(a^{560}\equiv1\) modulo 3, 11 et 17 séparément, puis concluez par le CRT. c) Comment s'appellent ces nombres, et pourquoi le test de Fermat est-il insuffisant ?
★★★★ Exercice 10 — lien informatique. Implémenter en Python.
a) L'exponentiation modulaire rapide puiss_mod(a, e, n) sans utiliser
pow(a,e,n).
b) Le théorème des restes chinois crt(residus, modules).
c) Vérifier sur l'exemple des 17 pirates.
d) Estimer le nombre de multiplications de puiss_mod pour un exposant de 2048
bits, et comparer à l'approche naïve.
Corrigés¶
Corrigé — Exercice 1
a) \(17\equiv2\pmod5\), donc \(17^2\equiv4\pmod5\). (Vérification : \(289 = 57\times5+4\) ✓)
b) \(-23 = -4\times7+5\), donc \(-23\equiv5\pmod7\).
c) \(2^{10} = 1024\). Par Fermat, \(2^{10}\equiv1\pmod{11}\) puisque 11 est premier. Vérification : \(1024 = 93\times11+1\) ✓
d) Somme des chiffres : \(1+2+3+4+5+6 = 21\), dont la somme des chiffres vaut 3. Donc \(123456\equiv3\pmod9\).
Corrigé — Exercice 2
a) \(\operatorname{pgcd}(3,7)=1\) : solution unique. \(3\times5 = 15\equiv1\pmod7\), donc \(x\equiv5\pmod7\).
b) \(\operatorname{pgcd}(4,6)=2\), qui divise 2 : deux solutions modulo 6. On simplifie : \(4x\equiv2\pmod6 \iff 2x\equiv1\pmod3\). Comme \(2^{-1}\equiv2\pmod3\), on a \(x\equiv2\pmod3\). Solutions modulo 6 : \(x\equiv2\) ou \(x\equiv5\).
Vérification : \(4\times2 = 8\equiv2\) ✓ ; \(4\times5=20\equiv2\) ✓
c) \(\operatorname{pgcd}(5,10)=5\), qui ne divise pas 3. Aucune solution.
(En effet \(5x \bmod 10\) ne vaut que 0 ou 5.)
Corrigé — Exercice 3
- \(\varphi(12) = \varphi(2^2\cdot3) = 12\times\frac12\times\frac23 = 4\). (Les inversibles sont 1, 5, 7, 11.)
- \(\varphi(35) = \varphi(5)\varphi(7) = 4\times6 = 24\).
- \(\varphi(100) = \varphi(2^2\cdot5^2) = 100\times\frac12\times\frac45 = 40\).
- \(\varphi(101) = 100\) (101 est premier).
- \(1001 = 7\times11\times13\), donc \(\varphi(1001) = 6\times10\times12 = 720\).
Corrigé — Exercice 4
a) \(7\) premier, \(7\nmid5\) : \(5^6\equiv1\pmod7\). \(100 = 16\times6+4\), donc \(5^{100}\equiv5^4\). \(5^2 = 25\equiv4\), \(5^4\equiv16\equiv2\pmod7\). \(5^{100}\equiv2\pmod7\).
b) \(2^{12}\equiv1\pmod{13}\). \(1000 = 83\times12+4\), donc \(2^{1000}\equiv2^4 = 16\equiv3\pmod{13}\).
c) \(3^{16}\equiv1\pmod{17}\). \(2026 = 126\times16+10\), donc \(3^{2026}\equiv3^{10}\).
\(3^2 = 9\) ; \(3^4 = 81 = 4\times17+13 \equiv -4\) ; \(3^8 \equiv 16 \equiv -1\) ; donc \(3^{10} = 3^8\cdot3^2 \equiv -9 \equiv 8\pmod{17}\).
\(3^{2026}\equiv8\pmod{17}\).
Corrigé — Exercice 5
Modules 3, 4, 5 deux à deux premiers entre eux ✓ \(N = 60\).
| \(i\) | \(n_i\) | \(a_i\) | \(N_i\) | \(N_i\bmod n_i\) | \(M_i\) |
|---|---|---|---|---|---|
| 1 | 3 | 1 | 20 | 2 | 2 |
| 2 | 4 | 2 | 15 | 3 | 3 |
| 3 | 5 | 3 | 12 | 2 | 3 |
(\(2\times2=4\equiv1\pmod3\) ✓ ; \(3\times3=9\equiv1\pmod4\) ✓ ; \(2\times3=6\equiv1\pmod5\) ✓)
\(238 = 3\times60+58\), donc \(x\equiv58\pmod{60}\).
Vérification : \(58 = 19\times3+1\) ✓ ; \(58 = 14\times4+2\) ✓ ; \(58 = 11\times5+3\) ✓
Info
On remarque que \(58 \equiv -2 \pmod{60}\), et que les trois congruences s'écrivent \(x\equiv-2\) modulo 3, 4 et 5. Repérer cette structure aurait donné la réponse immédiatement.
Corrigé — Exercice 6
Écriture décimale. Un entier \(N\) de chiffres \(c_k\dots c_1c_0\) s'écrit
Par 9. \(10\equiv1\pmod9\), donc \(10^i\equiv1\) pour tout \(i\), donc
\(N\) est divisible par 9 ssi la somme de ses chiffres l'est. \(\blacksquare\)
Par 3. Identique, puisque \(10\equiv1\pmod3\).
Par 11. \(10\equiv-1\pmod{11}\), donc \(10^i\equiv(-1)^i\), d'où
C'est la somme alternée en partant des unités. \(\blacksquare\)
Par 7. Écrivons \(N = 10a + u\) où \(u\) est le chiffre des unités et \(a\) le nombre formé des chiffres restants. La règle transforme \(N\) en \(a - 2u\).
Montrons l'équivalence :
On a \(N = 10a+u\). Calculons \(-2N = -20a-2u\), et
(vérification : \(-2(10a+u)+21a = -20a-2u+21a = a-2u\) ✓)
Comme \(7\mid21a\) :
- si \(7\mid N\), alors \(7\mid(-2N)\) donc \(7\mid(a-2u)\) ;
- si \(7\mid(a-2u)\), alors \(7\mid(-2N) = (a-2u)-21a\), et comme \(\operatorname{pgcd}(7,2)=1\), le théorème de Gauss donne \(7\mid N\).
\(\blacksquare\)
Vérification : \(364 \to 36-8 = 28 \to 2-16 = -14\), divisible par 7. Et \(364 = 52\times7\) ✓
Corrigé — Exercice 7
a) \(30 = 2\times3\times5\), facteurs premiers distincts. Il suffit de montrer \(n^5\equiv n\) modulo 2, 3 et 5, puis de conclure par le CRT (ou par le corollaire du théorème de Gauss).
- Modulo 2 : Fermat donne \(n^2\equiv n\), donc \(n^5 = (n^2)^2 n \equiv n^2\cdot n \equiv n\cdot n = n^2 \equiv n\).
- Modulo 3 : \(n^3\equiv n\), donc \(n^5 = n^3\cdot n^2 \equiv n\cdot n^2 = n^3\equiv n\).
- Modulo 5 : c'est directement le petit théorème de Fermat, \(n^5\equiv n\).
Les trois modules étant deux à deux premiers entre eux et divisant tous \(n^5-n\), leur produit 30 le divise. \(\blacksquare\)
b) \(42 = 2\times3\times7\).
- Modulo 2 : \(n^7 = (n^2)^3 n \equiv n^3\cdot n \equiv \dots \equiv n\).
- Modulo 3 : \(n^3\equiv n\), donc \(n^7 = (n^3)^2 n \equiv n^2\cdot n = n^3 \equiv n\).
- Modulo 7 : Fermat directement, \(n^7\equiv n\).
\(\blacksquare\)
Le motif général
\(n^k \equiv n \pmod m\) pour tout \(n\) si et seulement si \(m\) est sans facteur carré et si \((p-1)\mid(k-1)\) pour tout \(p\mid m\).
Pour \(m=30\) et \(k=5\) : les \(p-1\) valent 1, 2, 4, qui divisent bien 4 ✓ Pour \(m=42\) et \(k=7\) : 1, 2, 6 divisent 6 ✓
Corrigé — Exercice 8
a) \(N = 35\). Par substitution : \(x = 5t+2\), et \(5t+2\equiv3\pmod7\) donne \(5t\equiv1\pmod7\).
\(5^{-1}\pmod7\) : \(5\times3 = 15\equiv1\), donc \(5^{-1}\equiv3\). \(t\equiv3\pmod7\), soit \(t = 7s+3\).
Vérification : \(17 = 3\times5+2\) ✓ ; \(17 = 2\times7+3\) ✓
b) Les solutions sont \(17, 52, 87, \dots\), de la forme \(35s+17\).
\(1 \leqslant 35s+17\leqslant 1000\) donne \(-\frac{16}{35}\leqslant s \leqslant \frac{983}{35} = 28{,}09\).
Donc \(s\in\{0,1,\dots,28\}\) : 29 valeurs.
Vérification : la plus grande est \(35\times28+17 = 997 \leqslant 1000\) ✓ et la suivante serait \(1032 > 1000\) ✓
Corrigé — Exercice 9
a) Le petit théorème de Fermat affirme que si \(n\) est premier et \(n\nmid a\), alors \(a^{n-1}\equiv1\).
Par contraposée : si \(a^{n-1}\not\equiv1\pmod n\) pour un \(a\) premier avec \(n\), alors \(n\) n'est pas premier. \(\blacksquare\)
C'est un certificat de non-primalité : \(a\) est appelé témoin de Fermat.
b) Soit \(a\) premier avec \(561 = 3\times11\times17\).
- Modulo 3 : \(a^2\equiv1\) (Fermat). Or \(560 = 280\times2\), donc \(a^{560} = (a^2)^{280}\equiv1\).
- Modulo 11 : \(a^{10}\equiv1\). Or \(560 = 56\times10\), donc \(a^{560}\equiv1\).
- Modulo 17 : \(a^{16}\equiv1\). Or \(560 = 35\times16\), donc \(a^{560}\equiv1\).
Les trois modules sont deux à deux premiers entre eux et divisent tous \(a^{560}-1\) ; leur produit 561 le divise donc aussi (CRT) :
\(\blacksquare\)
Le point clé : \(560\) est divisible par \(2\), \(10\) et \(16\) — c'est-à-dire par \(p-1\) pour chacun des trois facteurs premiers.
c) Ces nombres s'appellent les nombres de Carmichael. Les plus petits sont 561, 1105, 1729, 2465, 2821, 6601.
Le test de Fermat est insuffisant parce qu'ils le passent pour toutes les bases premières avec eux : aucun tirage aléatoire de \(a\) ne les démasque (sauf à tomber sur un \(a\) non premier avec \(n\), ce qui revient à les factoriser).
Il en existe une infinité — résultat démontré en 1994 par Alford, Granville et Pomerance.
La solution pratique est le test de Miller-Rabin, qui exploite en plus la propriété « \(x^2\equiv1\pmod p\) implique \(x\equiv\pm1\) » démontrée à l'exercice 7c du chapitre 12. Aucun nombre composé ne passe Miller-Rabin pour plus d'un quart des bases : avec 40 tirages, la probabilité d'erreur est inférieure à \(4^{-40} \approx 10^{-24}\).
C'est le test utilisé pour générer les nombres premiers de RSA.
Corrigé — Exercice 10
a) et b)
def puiss_mod(a, e, n):
"""a**e mod n par exponentiation rapide."""
resultat = 1
a = a % n
while e > 0:
if e & 1:
resultat = (resultat * a) % n
a = (a * a) % n
e >>= 1
return resultat
def euclide_etendu(a, b):
r0, u0, v0 = a, 1, 0
r1, u1, v1 = b, 0, 1
while r1:
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 crt(residus, modules):
"""Solution du systeme x = residus[i] mod modules[i]."""
N = 1
for m in modules:
N *= m
x = 0
for a, m in zip(residus, modules):
Ni = N // m
d, Mi, _ = euclide_etendu(Ni, m)
assert d == 1, "modules non premiers entre eux"
x += a * Ni * Mi
return x % N
c) Vérifications.
assert puiss_mod(7, 100, 13) == 9
assert puiss_mod(3, 2026, 11) == 3
assert puiss_mod(9, 7, 143) == 48
assert puiss_mod(48, 103, 143) == 9
assert crt([2, 3, 2], [3, 5, 7]) == 23
assert crt([1, 2, 3], [3, 4, 5]) == 58
# les 17 pirates
x = crt([3, 10, 0], [17, 16, 15])
assert x == 3930
assert x % 17 == 3 and x % 16 == 10 and x % 15 == 0
print("OK")
d) Coût. L'exponentiation rapide traite un bit d'exposant par tour de boucle : pour un exposant de \(k = 2048\) bits, il y a 2048 itérations, chacune comportant un carré et, en moyenne une fois sur deux, une multiplication. Soit environ
L'approche naïve — multiplier \(a\) par lui-même \(e-1\) fois — en demanderait
Le rapport est de l'ordre de \(10^{613}\). Sans exponentiation rapide, RSA n'existerait tout simplement pas.
Ce que ce chapitre a rassemblé
RSA mobilise la totalité du bloc arithmétique :
- division euclidienne et PGCD (ch. 11) pour choisir \(e\) ;
- Euclide étendu (ch. 12) pour calculer \(d\) ;
- congruences, Euler et CRT (ch. 13) pour chiffrer, déchiffrer et accélérer ;
- exponentiation rapide (ch. 01, exercice 8) pour que tout cela tienne en quelques millisecondes.
C'est la raison d'être de ces trois chapitres dans le programme d'une école d'informatique.
Fin de la partie Algèbre. Chapitre suivant : Analyse 1 — ANAL11.