Fermat, Euler et les restes chinois
Calculer modulo n, c'est calculer sur une horloge à n heures. Sur ces horloges, les puissances finissent toujours par revenir à 1, chaque nombre premier avec n a un inverse, et plusieurs petites horloges valent une grande. Trois théorèmes vieux de plusieurs siècles, ceux de Fermat, d'Euler et des restes chinois, qui font aujourd'hui tourner la cryptographie de nos cartes bancaires. Cinq planches pour les voir, les comprendre et s'en servir.
Vue d'ensemble
On écrit a ≡ b (mod n) lorsque a et b ont le même reste dans la division par n. Les congruences se manipulent comme des égalités : on peut les additionner et les multiplier. Trois théorèmes structurent ce calcul :
| Théorème | Énoncé | Ce qu'il permet |
|---|---|---|
| Fermat (1640) | si p est premier et ne divise pas a, alors aᵖ⁻¹ ≡ 1 (mod p) | réduire les exposants, tester la primalité |
| Euler (1763) | si a est premier avec n, alors aφ(n) ≡ 1 (mod n) | étendre Fermat à tout n, construire RSA |
| Wilson (1770) | p est premier si et seulement si (p − 1)! ≡ −1 (mod p) | caractériser les nombres premiers |
| Restes chinois | si m et n sont premiers entre eux, connaître x mod m et x mod n, c'est connaître x mod mn | découper un grand calcul en petits |
Le petit théorème de Fermat : les puissances tournent en rond
Que deviennent a, a², a³… quand on ne garde que leur reste modulo un nombre premier p ?
Il n'y a que p − 1 restes non nuls possibles, donc la suite des puissances finit par se répéter. Elle revient toujours à 1. Le plus petit exposant k tel que aᵏ ≡ 1 est l'ordre de a, et il divise toujours p − 1 (c'est le théorème de Lagrange sur les groupes). En particulier aᵖ⁻¹ ≡ 1 (mod p) : c'est le petit théorème de Fermat, énoncé en 1640 dans une lettre à Frénicle, sans démonstration.
L'indicatrice d'Euler : Fermat pour tous les modules
Et si le module n'est pas premier ?
Modulo 12, la base 2 ne revient jamais à 1 : ses puissances valent 2, 4, 8, 4, 8… Seuls les nombres premiers avec n se comportent bien. Euler compte ces nombres : φ(n) est le nombre d'entiers de 1 à n premiers avec n, et aφ(n) ≡ 1 (mod n) pour tout a premier avec n. La preuve est une belle idée : multiplier par a permute les φ(n) nombres premiers avec n. Leur produit P ne change donc pas, d'où aφ(n)·P ≡ P, et l'on simplifie par P.
Les inverses modulo n et le théorème de Wilson
Peut-on diviser sur une horloge ?
Diviser par a, c'est multiplier par un nombre b tel que ab ≡ 1 (mod n). Un tel inverse existe exactement quand a est premier avec n, et la relation de Bézout le fournit : l'algorithme d'Euclide étendu trouve u et v avec au + nv = 1, donc au ≡ 1. Modulo un nombre premier p, tous les restes non nuls ont un inverse. Rangés en paires {x, x⁻¹}, ils se simplifient deux à deux dans le produit (p − 1)!. Seuls 1 et p − 1 sont leur propre inverse, d'où le théorème de Wilson : (p − 1)! ≡ −1 (mod p).
Le théorème des restes chinois : plusieurs petites horloges en valent une grande
« Un nombre laisse 2 quand on le divise par 3, 3 par 5, et 2 par 7. Quel est-il ? »
Ce problème vient du Sunzi suanjing, un manuel chinois des IIIᵉ–Vᵉ siècles. Si les modules sont premiers entre eux deux à deux, il y a exactement une solution modulo leur produit, et on la construit : x = Σ rᵢMᵢyᵢ, où Mᵢ est le produit des autres modules et yᵢ l'inverse de Mᵢ modulo mᵢ (planche 3). Vu autrement : compter k = 0, 1, 2… sur deux horloges à la fois, c'est avancer en diagonale sur une grille. Si les deux tailles sont premières entre elles, la diagonale passe par toutes les cases avant de revenir au départ.
Le problème de Sunzi, avec vos restes
Signature : RSA, les nombres de Carmichael et la puissance rapide
Les trois théorèmes réunis protègent les communications du monde entier, et permettent de reconnaître un nombre premier de mille chiffres en une fraction de seconde.
On choisit deux nombres premiers p et q, on publie n = pq et un exposant e premier avec φ(n) = (p − 1)(q − 1). On garde secret l'inverse d de e modulo φ(n). Chiffrer un message m (un nombre inférieur à n), c'est calculer c = mᵉ mod n ; déchiffrer, c'est calculer cd mod n. Le théorème d'Euler garantit que l'on retrouve m. Pour trouver d, il faut φ(n), donc p et q : connaître n ne suffit pas tant qu'on ne sait pas le factoriser.
Fermat donne un test : si an−1 ≢ 1 (mod n) pour une base a, alors n n'est certainement pas premier. Mais la réciproque est fausse. Certains nombres composés, les nombres de Carmichael (1910), passent le test pour toutes les bases premières avec eux. Le plus petit est 561 = 3 × 11 × 17. Le test de Miller-Rabin (1976-1980) affine Fermat en examinant aussi les racines carrées de 1 : un nombre composé le passe pour au plus un quart des bases, si bien que vingt bases au hasard suffisent en pratique.
Calculer ae mod n en multipliant e fois par a serait impossible pour les exposants de RSA, qui ont des centaines de chiffres. L'exponentiation rapide lit l'exposant en binaire : on élève au carré à chaque chiffre, et l'on multiplie par a quand le chiffre vaut 1. Le nombre d'opérations ne croît que comme le nombre de chiffres de e : environ 2 log₂ e multiplications au lieu de e.
Une brève histoire
En résumé
Les puissances reviennent à 1
Modulo p premier, aᵖ⁻¹ ≡ 1 ; modulo n quelconque, aφ(n) ≡ 1 si a est premier avec n. L'ordre de a divise toujours φ(n).
Diviser sur une horloge
a est inversible modulo n exactement quand pgcd(a, n) = 1, et Euclide étendu calcule l'inverse. Modulo p, (p − 1)! ≡ −1 : c'est Wilson.
Découper pour régner
Si les modules sont premiers entre eux, plusieurs petites horloges valent une grande. RSA, les tests de primalité et l'exponentiation rapide reposent sur ces trois idées.
Pour aller plus loin
Une preuve par les colliers. Avec a couleurs, il y a aᵖ colliers de p perles. Les a colliers unicolores mis à part, les autres se regroupent par paquets de p rotations distinctes (p premier). Donc p divise aᵖ − a : c'est le théorème de Fermat.
Logarithme discret. Retrouver k à partir de aᵏ mod p est très difficile. C'est la base de l'échange de clés de Diffie et Hellman (1976).
Liens. PGCD et relation de Bézout, congruences, nombres premiers de Mersenne (test de Lucas-Lehmer), encryptage et chiffrement, structures algébriques (le groupe des inversibles modulo n), modules sur un anneau (les restes chinois).