Arithmétique modulaire

Un relevé chiffré se calcule sur des entiers

Le distributeur doit retrouver le relevé exact, au litre près : un déchiffrement qui rendrait 1 233,999 litres au lieu de 1 234 ne servirait à rien. Les nombres à virgule de la machine ne garantissent pas cette exactitude : en Python, 0.1 + 0.2 == 0.3 est faux, et le chapitre Les nombres à virgule flottante montre pourquoi, bit par bit. Un chiffrement calcule donc sur des entiers, que la machine range sans aucune erreur.

Sur les entiers, une opération familière perd sa garantie : la division. Dans les réels, $3x = 5$ a pour solution $5/3$ ; dans les entiers, elle n'en a aucune, puisque 3 ne divise pas 5. Le calcul sur les restes, que ce chapitre construit, rebat encore les cartes : on y verra qu'il existe un entier $x$ tel que $7x$ laisse le reste 3 dans la division par 26, à savoir $x = 19$, et qu'aucun ne convient pour $13x$. Savoir quand une division est permise, et par quoi la remplacer, occupe une bonne part du chapitre.

Une horloge montre de quoi ce calcul est fait. Partir de midi, la case 0 en haut du cadran, et avancer d'une heure, de treize heures ou de vingt-cinq heures amène l'aiguille au même endroit : sur le 1. Ce qui se conserve d'un tour à l'autre n'est pas le nombre d'heures parcourues, c'est le reste, et lui seul. En regardant l'aiguille, impossible de dire combien de tours elle a faits : cette information est perdue, et aucun calcul ne la retrouve. La cryptographie ne s'appuie pas sur une telle perte, puisque le destinataire doit retrouver le message entier : elle emploie des opérations sur les restes qui ne perdent rien, et que seul le détenteur d'un secret sait défaire vite.

Divisibilité et division euclidienne

L'unicité du couple $(q, r)$ est ce qui rend tout le reste possible. Par exemple, $250 = 13 \times 19 + 3$ : $13 \times 19 = 247$, et le reste 3 est bien entre 0 et 12. En Python, a // b donne $q$ et a % b donne $r$ : ce sont les opérateurs de quotient entier et de reste du chapitre Les bases de Python.

PGCD et algorithme d'Euclide

Le pgcd est le plus grand entier divisant $a$ et $b$ ; le ppcm le plus petit multiple commun positif. Ils sont liés par $\operatorname{pgcd}(a, b) \times \operatorname{ppcm}(a, b) = |ab|$.

Deux entiers sont premiers entre eux si leur pgcd vaut 1. Ce n'est pas la même chose qu'être premiers : 8 et 9 sont premiers entre eux, et aucun des deux n'est premier.

Cette observation se démontre en trois lignes, et il vaut la peine de les suivre : sans elle, l'algorithme n'est qu'une recette.

Le point de départ est la division euclidienne $a = bq + r$, récrite $r = a - bq$.

Soit $d$ un diviseur commun à $a$ et à $b$. Il divise alors $a - bq$, c'est-à-dire $r$ : tout diviseur commun de $a$ et $b$ est aussi un diviseur commun de $b$ et $r$.

Réciproquement, soit $d$ un diviseur commun à $b$ et à $r$. Il divise $bq + r$, c'est-à-dire $a$ : tout diviseur commun de $b$ et $r$ est aussi un diviseur commun de $a$ et $b$.

Les deux couples ont donc exactement les mêmes diviseurs communs, et en particulier le même plus grand. Remplacer $(a, b)$ par $(b, r)$ ne perd rien, et fait strictement décroître le second terme : c'est ce qui garantit à la fois la justesse et la terminaison.

C'est un des plus vieux algorithmes connus, et il reste remarquablement rapide : le nombre de divisions est en $O(\log(\min(a, b)))$, c'est-à-dire proportionnel au nombre de chiffres. La notation $O$ est celle du chapitre sur la complexité. Sur des nombres de 600 chiffres, l'algorithme pose en moyenne un peu plus d'un millier de divisions, jamais plus de trois mille, et termine en une fraction de milliseconde.

Euclide étendu et Bézout

L'algorithme d'Euclide étendu calcule ce couple $(u, v)$ en même temps que le pgcd. Ce n'est pas une curiosité théorique : c'est exactement ce qui permettra de calculer une clé privée RSA. Une ligne de Python en donne le résultat, et la section « Vérifier à la machine » s'en sert ; mais il faut savoir dérouler le calcul à la main. C'est le seul moyen de comprendre d'où sortent $u$ et $v$, et ce calcul revient dans tout le chapitre.

La descente, puis la remontée. Descendre. Poser les divisions euclidiennes successives, chacune sous la forme dividende = diviseur × quotient + reste, jusqu'à un reste nul. Le dernier reste non nul est le pgcd.

Remonter. Partir de la ligne qui donne ce pgcd, isolé à gauche. Puis, ligne après ligne en remontant, remplacer chaque reste par son expression tirée de la ligne du dessus. À la fin il ne reste que $a$ et $b$, et leurs coefficients sont $u$ et $v$.

Congruences : calculer modulo $n$

Beaucoup de questions ne demandent pas un résultat, seulement un reste. L'heure qu'il sera dans 50 heures, le jour de la semaine dans 100 jours, la case d'une table de hachage, la lettre obtenue après un décalage de l'alphabet. Dans tous ces cas, le quotient ne sert à rien. Calculer le résultat exact puis prendre son reste est un détour coûteux. Les congruences sont le langage qui permet de travailler directement sur les restes, sans jamais quitter les petits nombres.

La notation se lit à voix haute en deux morceaux : le symbole $\equiv$ se dit « est congru à », et le $[n]$ se dit « modulo $n$ ». Ce $[n]$ porte sur toute l'égalité, jamais sur le seul membre de droite. D'autres ouvrages écrivent $a \equiv b \pmod n$ : c'est la même chose, et ce chapitre s'en tient aux crochets.

Ce que la définition écarte : $\equiv$ n'est pas $=$. Deux nombres congrus restent deux nombres différents, et rien n'autorise à remplacer l'un par l'autre hors d'un calcul modulo $n$.

Ce qu'il faut y voir : une case du cadran ne porte pas un nombre, elle porte une infinité de nombres, ceux qui laissent le même reste. La vérification tient en deux soustractions : $41 - 15 = 26$ et $15 - (-11) = 26$, tous deux multiples de 26. Une congruence se contrôle toujours ainsi, en soustrayant.

La congruence est compatible avec l'addition et la multiplication : si $a \equiv b \ [n]$ et $c \equiv d \ [n]$, alors $a + c \equiv b + d \ [n]$ et $ac \equiv bd \ [n]$. Remplacer un nombre par un autre de la même case ne change donc pas la case du résultat, et on peut réduire à chaque étape d'un calcul, ce qui évite de manipuler des nombres gigantesques. Exemple : $41 \times 15$ modulo 26. Comme $41 \equiv 15$, le produit tombe dans la même case que $15 \times 15 = 225 = 8 \times 26 + 17$, donc $41 \times 15 \equiv 17 \ [26]$, sans avoir calculé $615$. De même, puisque $100 = 14 \times 7 + 2$, on sera dans 100 jours le même jour de la semaine que dans 2 jours.

Réduire chaque terme ne dispense pas de réduire le résultat : modulo 11, $20 + 30 \equiv 9 + 8 = 17$, qui se réduit encore en 6. Un résultat qui sort de $[0 ; n - 1]$ n'est pas faux, mais il n'est pas fini, et la comparaison avec un reste attendu échouera.

Comparer les deux dernières réponses, et dire ce que la preuve par neuf laisse passer : deux chiffres échangés gardent la même somme. La clé d'un IBAN, calculée modulo 97, attrape cette erreur-là.

L'inverse modulaire

Cette condition sur le pgcd n'est pas une clause technique : elle se voit. Avancer de $a$ en $a$ sur le cadran revient à parcourir les multiples de $a$, et deux cas seulement se présentent.

Une case jamais atteinte a un revers : les cases atteintes le sont par plusieurs nombres de pas différents (1, 3, 5… pas de 13 mènent tous à la case 13), si bien qu'en voyant la case d'arrivée on ne peut plus dire combien de pas ont été faits, comme les tours sur l'horloge du début. Avec un pas de 7, rien ne se perd : chaque case est atteinte par un seul nombre de pas entre 0 et 25, et l'inverse permet de revenir en arrière. Le curseur du modulo, placé au-dessus de celui du pas, montre d'ailleurs que le phénomène ne tient pas au 26 : un pas de 13 modulo 27 fait, lui, le tour complet.

Le lien avec l'inverse tient en une ligne : après $k$ pas de 7 depuis 0, le tracé est sur la case $7k \bmod 26$. Tomber sur 1, c'est donc trouver $k$ tel que $7k \equiv 1 \ [26]$, c'est-à-dire l'inverse de 7. Ici $k = 15$, puisque $7 \times 15 = 105 = 4 \times 26 + 1$.

Cet inverse sert à simplifier quand c'est permis. Pour résoudre $7x \equiv 3 \ [26]$, multiplier les deux membres par 15 donne $105x \equiv 45$, c'est-à-dire $x \equiv 19 \ [26]$, puisque $105 \equiv 1$ et $45 = 26 + 19$. Contrôle : $7 \times 19 = 133 = 5 \times 26 + 3$. Multiplier par l'inverse de 7, c'est exactement « diviser par 7 » ; quand l'inverse n'existe pas, cette division n'a pas de sens.

Nombres premiers

Le crible d'Ératosthène

Pour lister tous les premiers jusqu'à $N$ : on écrit les entiers de 2 à $N$, on garde le plus petit non barré, on barre tous ses multiples, on recommence. On peut s'arrêter dès que le carré du candidat dépasse $N$.

À la main, le crible s'arrête vite. La machine le pousse jusqu'à 100 000 et montre ce que la main ne voit pas : les premiers se raréfient, sans jamais s'arrêter.

Familles remarquables

Factoriser est difficile, et tout repose là-dessus

Multiplier deux nombres premiers de 300 chiffres prend une fraction de microseconde. Retrouver ces deux facteurs à partir du produit est, à ce jour, hors de portée de toute machine existante.

C'est l'asymétrie fondamentale sur laquelle RSA est bâti : une opération immédiate dans un sens, sans méthode praticable dans l'autre.

La méthode la plus simple, la division d'essai, essaie les diviseurs 2, 3, 4… tant que leur carré ne dépasse pas le nombre : un diviseur plus grand que la racine en apparie un plus petit, déjà essayé. Le bloc suivant la chronomètre sur trois produits de deux premiers.

La division d'essai n'est pas la meilleure attaque connue : des méthodes bien plus fines ont factorisé en 2020 un nombre de 250 chiffres, au prix de milliers d'années de calcul cumulées. Leur coût croît encore trop vite pour 600 chiffres, et c'est lui, non la division d'essai, qui fixe la taille des clés.

Ce que « difficile » veut dire, et ne veut pas dire. Il n'est pas démontré que factoriser est intrinsèquement difficile : c'est une difficulté constatée, pas prouvée. Un algorithme efficace pourrait exister et n'avoir pas été trouvé ; ce chapitre et le suivant s'appuient sur un constat, pas sur un théorème.

On sait en revanche que l'algorithme de Shor factorise en temps polynomial sur un ordinateur quantique. La menace n'est pas théorique, elle est technologique, et elle motive la cryptographie post-quantique, qui repose sur d'autres problèmes difficiles, pas sur la factorisation.

Euler et Fermat

La section sur l'inverse modulaire a laissé une question ouverte. Un élément est inversible modulo $n$ quand son pgcd avec $n$ vaut 1 : combien y en a-t-il ? Ce nombre porte un nom, et c'est lui qui servira de module pour calculer la clé privée RSA, comme $3828$ dans l'exemple d'Euclide étendu.

La lettre $\varphi$ se lit « phi », et $\varphi(n)$ se dit « phi de $n$ ». Elle compte donc les entiers de l'intervalle $[1 ; n]$ dont le pgcd avec $n$ vaut 1, c'est-à-dire exactement les éléments inversibles modulo $n$. Sur $n = 12$ : les candidats sont 1, 5, 7 et 11, et aucun autre, car tous les autres partagent un 2 ou un 3 avec 12. Donc $\varphi(12) = 4$.

La première égalité est immédiate : si $p$ est premier, tous les entiers de 1 à $p - 1$ lui sont premiers, et seul $p$ ne l'est pas.

La seconde se compte, et ce décompte mérite d'être fait une fois, parce que c'est lui qui donne le module de la clé privée RSA.

Parmi les $pq$ entiers de 1 à $pq$, un entier n'est pas premier avec $pq$ exactement lorsqu'il est multiple de $p$ ou multiple de $q$. Il y a $q$ multiples de $p$ (à savoir $p, 2p, \dots, qp$) et $p$ multiples de $q$. Le seul entier compté deux fois est $pq$ lui-même, qui est multiple des deux.

Le nombre d'entiers à retirer vaut donc $p + q - 1$, et il reste

$\varphi (pq) = pq - p - q + 1 = (p - 1)(q - 1)$

Un entier multiple à la fois de $p$ et de $q$ est multiple de $pq$, et entre 1 et $pq$ il n'y en a qu'un. Sur un petit cas, $p = 3$ et $q = 5$ : parmi les entiers de 1 à 15, les multiples de 3 sont 3, 6, 9, 12, 15 (cinq, soit $q$) et ceux de 5 sont 5, 10, 15 (trois, soit $p$). Seul 15 est compté deux fois, il faut donc en retirer $5 + 3 - 1 = 7$, et il reste $\varphi(15) = 8 = 2 \times 4$. Sur le module RSA du chapitre suivant, $N = 3953 = 59 \times 67$, la formule donne $\varphi(3953) = 58 \times 66 = 3828$ : c'est le 3828 de l'exemple d'Euclide étendu.

En clair : élever un nombre à la puissance $\varphi(n)$ ramène toujours à 1, à la seule condition que ce nombre n'ait aucun facteur commun avec $n$. C'est un retour garanti au point de départ. Dépasser cet exposant ne fait que recommencer le même tour : en écrivant l'exposant $k = q\varphi(n) + r$, on obtient $a^k = \left(a^{\varphi(n)}\right)^q \times a^r \equiv 1^q \times a^r = a^r$, donc seul le reste de l'exposant modulo $\varphi(n)$ compte. Par exemple, modulo 11, qui est premier, $\varphi(11) = 10$, et $3^{23} \equiv 3^{3} = 27 \equiv 5 \ [11]$.

C'est ce second théorème qui fait fonctionner RSA : c'est lui qui fera disparaître le facteur parasite au moment du déchiffrement.

L'exponentiation modulaire rapide

Calculer $a^d \operatorname{mod} n$ avec $d$ de 600 chiffres semble impossible. Il ne l'est pas, grâce à une idée simple : élever au carré plutôt que multiplier une fois de plus. Le coût ne croît alors plus qu'avec le nombre de chiffres de l'exposant.

Un exemple, avec les nombres de l'exemple RSA du chapitre suivant : $65^{13} \bmod 3953$, où $3953 = 59 \times 67$ et où $13$ est l'exposant public déjà rencontré avec Euclide étendu. L'écriture binaire de l'exposant, $13 = 1101_2 = 8 + 4 + 1$, donne $65^{13} = 65^{8} \times 65^{4} \times 65$. Trois élévations au carré fournissent $65^2$, $65^4$ et $65^8$, chacune réduite modulo 3953 avant la suivante :

$65^2 = 4\,225 \equiv 272$, puis $272^2 = 73\,984 \equiv 2\,830$, puis $2\,830^2 = 8\,008\,900 \equiv 122$. Donc $65^{4} \equiv 2\,830$ et $65^{8} \equiv 122 \ [3953]$.

Il reste deux multiplications : $122 \times 2\,830 = 345\,260 = 87 \times 3953 + 1\,349$, puis $1\,349 \times 65 = 87\,685 = 22 \times 3953 + 719$, d'où $65^{13} \equiv \mathbf{719} \ [3953]$. Cinq opérations au total, et aucun nombre intermédiaire de plus de sept chiffres, alors que $65^{13}$ écrit en entier en compterait vingt-quatre. Réduire à chaque étape est ce qui rend le calcul possible.

Huit opérations contre quarante-quatre, sur un exposant de deux chiffres. Sur un exposant de six cents chiffres, comme ceux de la cryptographie, le calcul naïf demanderait plus d'opérations qu'il n'y a d'atomes dans l'univers, et la méthode par carrés en demande quelques milliers.

Vérifier à la machine

Chaque calcul de ce chapitre se fait à la main, et c'est ainsi qu'il se comprend. Une fois fait, il se vérifie en une ligne, comme on vérifie une formule de tableur :

• math.gcd(a, b) donne le pgcd ;
• pow(a, -1, n) donne l'inverse de a modulo n, et refuse avec une erreur quand il n'existe pas ;
• pow(a, k, n) donne $a^k$ modulo $n$, par carrés successifs ;
• a % n donne le reste, toujours entre 0 et $n - 1$ pour un n positif.

Programmer soi-même ces algorithmes, Euclide étendu ou l'exponentiation rapide, est l'objet des exercices du thème. La version la plus courte d'Euclide étendu est récursive : une fonction qui s'appelle elle-même, comme la factorielle du chapitre Bien écrire une fonction.

La méthode

1. Écrire la division euclidienne sous la forme $a = bq + r$ avec $0 \leq r < b$. Toutes les erreurs de signe viennent de son oubli.
2. Poser Euclide en colonnes, une division par ligne. Le dernier reste non nul est le pgcd.
3. Pour Bézout, remonter les égalités une à une, en substituant les restes sans développer les produits, ou en appliquant la règle $(\alpha, \beta) \leftarrow (\beta, \alpha - \beta q)$.
4. Réduire à chaque étape dans un calcul modulaire, résultat compris. Ne jamais développer une grande puissance.
5. Vérifier qu'un facteur est inversible avant de le simplifier dans une congruence. Il ne l'est que s'il est premier avec le module.
6. Pour une puissance modulaire, réduire l'exposant modulo $\varphi(n)$ quand la base est première avec $n$, puis procéder par carrés successifs en suivant l'écriture binaire.
7. Contrôler un inverse en multipliant ($a \times x \bmod n$ vaut 1), un couple de Bézout en recalculant $au + bv$, puis vérifier avec pow ou math.gcd.

Mettre en pratique

Trois calculs pour finir, qui traversent le chapitre et ne reprennent aucun nombre du cours.

Les trois réponses se contrôlent avec math.gcd et pow, comme dans la section précédente.