Compter en tournant en rond — et ce que cela permet de faire
Deux entiers sont congrus modulo n lorsque leur différence est un multiple de n : on écrit a ≡ b (mod n). Autrement dit, on décide d'oublier tout ce qu'un nombre a de plus qu'un reste. Cette amnésie volontaire, introduite par Gauss en 1801 dans les Disquisitiones arithmeticae, transforme l'ensemble infini des entiers en une horloge à n positions où l'on peut encore additionner et multiplier. Les cinq planches qui suivent construisent cette horloge, vérifient qu'elle est cohérente, mesurent ce qui s'y conserve, puis suivent la congruence dans les objets qui nous entourent : un ISBN, un IBAN, un jour de la semaine, et enfin le chiffrement qui protège une connexion.
La droite des entiers s'enroule : après n pas, on retombe au même endroit. Chaque rayon de la spirale porte une classe de congruence, c'est-à-dire tous les entiers qui laissent le même reste dans la division par n.
Ce que dit la planche. La division euclidienne a = n·q + r avec 0 ≤ r < n place chaque entier sur un rayon, et un seul. Deux entiers sont congrus modulo n si et seulement si n divise leur différence : la définition par les restes et la définition par la divisibilité sont la même. L'épreuve tire au hasard des couples (a, b) et des modules, puis compare les deux critères un à un.
La congruence n'est pas seulement une façon de ranger les entiers : elle survit aux opérations. Si a ≡ a′ et b ≡ b′ modulo n, alors a + b ≡ a′ + b′ et a·b ≡ a′·b′. On peut donc calculer directement sur les classes — d'où les deux tables ci-dessous.
Ce que dit la planche. Dans la table de multiplication, une ligne qui contient un 1 signale un inversible ; une case nulle hors de la première ligne signale un diviseur de zéro, deux nombres non nuls dont le produit est nul. Un entier a est inversible modulo n exactement quand pgcd(a, n) = 1 — la page vérifie cette équivalence sur les n classes. Quand n est premier, aucun diviseur de zéro ne subsiste et toutes les classes non nulles sont inversibles : on peut diviser, et ℤ/nℤ est un corps. Quand n est composé, la table se troue.
On part de a et on multiplie sans fin par a. Comme il n'y a que n restes possibles, la suite des puissances finit par se répéter : elle boucle. La longueur de la boucle s'appelle l'ordre de a, et le théorème de Lagrange impose qu'elle divise φ(n), le nombre de classes inversibles.
Ce que dit la planche. Le théorème d'Euler affirme que aφ(n) ≡ 1 (mod n) dès que pgcd(a, n) = 1 ; lorsque n est premier, φ(n) = n − 1 et l'on retrouve le petit théorème de Fermat. La page recalcule l'ordre de chaque classe inversible par multiplications successives et vérifie que tous divisent φ(n). Attention à la réciproque : elle est fausse. Le bouton ci-dessous exhibe 561 = 3 × 11 × 17, composé, qui se comporte pourtant comme un nombre premier pour toutes les bases premières avec lui — le premier des nombres de Carmichael.
Quatre usages ordinaires, chacun réduit à un reste. On peut changer un chiffre pour voir la clé s'effondrer, déplacer une date, ou casser la bijection des restes chinois en donnant aux deux modules un facteur commun.
Ce que dit l'onglet. Une clé de contrôle ajoute au message le chiffre qui annule un reste. Toute erreur portant sur un seul caractère change la somme pondérée d'une quantité non nulle modulo n : elle est donc toujours vue. Les transpositions de deux caractères voisins, elles, dépendent des poids. Avec l'alternance 1, 3 de l'ISBN-13, l'écart vaut 2(x − y) modulo 10 : il s'annule quand les deux chiffres diffèrent de 5, et ces transpositions-là passent inaperçues. Les poids de l'IBAN, puissances de 10 modulo 97, ne présentent pas ce défaut. Les deux épreuves ci-dessus sont exhaustives, pas échantillonnées.
Ce que dit l'onglet. Le calendrier grégorien se répète exactement tous les 400 ans, parce que 400 années contiennent 146 097 jours et que ce nombre est divisible par 7 : 146 097 = 20 871 × 7. Tout le calendrier tient donc dans une congruence modulo 7, que la congruence de Zeller met en formule. Conséquence mesurable : sur un cycle complet, les 13 du mois ne se répartissent pas également entre les sept jours, et le vendredi l'emporte de peu. La page compte les 4 800 occurrences elle-même et confronte sa formule à l'horloge du navigateur sur des dizaines de milliers de dates tirées au hasard.
Ce que dit l'onglet. Le tableau croise les restes modulo m₁ et modulo m₂. Quand les deux modules sont premiers entre eux, les m₁·m₂ entiers de 0 à m₁m₂ − 1 remplissent toutes les cases exactement une fois : connaître les deux restes revient à connaître le nombre. C'est le théorème des restes chinois, énoncé par Sun Zi vers le IIIe siècle. Dès que les modules partagent un facteur, le remplissage ne couvre plus que le ppcm des cases et le système n'a de solution que si les restes s'accordent sur ce facteur commun.
Ce que dit l'onglet. Un nombre écrit en base dix vaut Σ cₖ·10k. Tout critère de divisibilité se lit donc dans la suite des restes de 10k modulo d, tracée en roue ci-dessus. Pour 3 et 9, tous ces restes valent 1 : on somme les chiffres. Pour 11, ils alternent 1 et −1 : on somme en alternant les signes. Pour 7 et 13, le cycle a six termes et le critère devient un découpage en tranches de trois chiffres. La page compare la somme pondérée au reste réel du nombre entier, calculé en arithmétique exacte.
Élever à une puissance modulo n est facile ; revenir en arrière ne l'est pas, sauf à connaître la factorisation de n. Tout le chiffrement RSA tient dans cet écart. La machine ci-dessous fabrique de vraies clés, chiffre un vrai message, puis la même page se retourne contre elle et casse la clé pour de bon — en mesurant ce que cela coûte.
Ce que dit la signature. Les clés sont réelles : d est bien l'inverse de e modulo φ(n), et le déchiffrement fonctionne parce que med ≡ m (mod n), ce qui n'est rien d'autre que le théorème d'Euler de la planche 3. La seconde courbe factorise vraiment les modules produits, par divisions d'essai puis par la méthode ρ de Pollard, et compte les opérations : en échelle logarithmique, les pentes mesurées se comparent aux exposants théoriques 1/2 et 1/4 par bit. Prolongée jusqu'aux 2048 bits d'une vraie clé, la première méthode demanderait de l'ordre de 21024 opérations. Réserve honnête : cette machine chiffre un caractère par bloc et sans remplissage aléatoire, ce qui la rend triviale à casser par simple dictionnaire — un RSA d'usage réel utilise des modules de plusieurs centaines de chiffres et un remplissage normalisé. La planche montre le mécanisme, pas un chiffrement sûr.