Arithmétique modulaire

Pourquoi de l'arithmétique au XXI^e siècle

L'objection est naturelle : on dispose des réels, des complexes, des vecteurs, pourquoi revenir aux entiers ?

Divisibilité et division euclidienne

L'unicité du couple $(q, r)$ est ce qui rend tout le reste possible. En Python, a // b donne $q$ et a % b donne $r$ : ce sont les opérateurs de division entière et de reste du parcours 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 est celle de l'analyse d'algorithmes, abordée dans le parcours Algorithmique. Sur des nombres de 600 chiffres, l'algorithme pose un peu plus d'un millier de divisions 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.

Le code ci-dessous le fait en trois lignes, mais il faut savoir le dérouler à la main. C'est le seul moyen de comprendre d'où sortent $u$ et $v$, et ce calcul revient dans tout le chapitre.

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.

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$.

Travailler modulo $n$, c'est compter sur une horloge : passé $n - 1$, on revient à zéro. Toute l'étrangeté de l'arithmétique modulaire vient de là, et elle cesse d'être étrange dès qu'on voit le cercle.

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$ et $c \equiv d$, alors $a + c \equiv b + d$ et $ac \equiv bd$. On peut donc réduire à chaque étape d'un calcul, ce qui évite de manipuler des nombres gigantesques.

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.

Ce qu'il faut suivre du regard, c'est le tracé : tant qu'il n'est pas refermé, il reste des cases à visiter. Le second cas est l'exact opposé, avec un pas qui partage un diviseur avec 26.

Le tracé se referme immédiatement, et la case 1 n'a jamais été touchée : c'est cela, ne pas être inversible. Une case jamais atteinte, c'est une information définitivement perdue.

Vérification

1.Deux nombres premiers entre eux sont…

deux nombres dont le pgcd vaut 1, premiers ou nondeux nombres premiersdeux nombres impairs

2.Le théorème de Bézout garantit l'existence de u et v tels que au + bv = pgcd(a, b). À quoi cela sert-il concrètement ?

À tester si un nombre est premierÀ factoriser un grand nombreÀ calculer un inverse modulaire, donc une clé privée RSA

3.La remontée d'Euclide produit presque toujours un coefficient négatif. Est-ce une erreur ?

Non, c'est inévitable : deux termes positifs dépassant 1 ne peuvent pas totaliser 1Non, mais il faut alors recommencer dans l'autre sensOui, cela signale une faute de signe

4.Calculer a mod n quand a est négatif, en Python et en C, donne…

des résultats différents : Python rend un reste positif, C garde le signe du dividendele même résultat dans les deux langagesune erreur en Python

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$.

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.

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 ? La réponse détermine le nombre d'exposants publics utilisables dans RSA, et elle porte un nom.

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 fixe la taille de l'espace des clés 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)$

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 une remise à zéro garantie. Dépasser cet exposant ne fait que recommencer le même tour, ce qui revient à dire que seul le reste de l'exposant modulo $\varphi(n)$ compte.

C'est ce second théorème, et lui seul, 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. Ça ne l'est pas, grâce à une idée simple : élever au carré plutôt que multiplier une fois de plus.

Pour $a^{13}$, l'écriture binaire de l'exposant, $13 = 1101_2 = 8 + 4 + 1$, donne $a^{13} = a^8 \times a^4 \times a$. Trois élévations au carré successives fournissent $a^2$, $a^4$ et $a^8$, puis deux multiplications les assemblent : cinq multiplications au lieu de douze. L'écart devient vertigineux sur un grand exposant, dont le coût ne croît plus qu'avec le nombre de chiffres.

Le même calcul en entier, avec les nombres du RSA de la fin du chapitre : $65^{17} \bmod 3233$. L'exposant s'écrit $17 = 10001_2 = 16 + 1$, donc $65^{17} = 65^{16} \times 65$. Quatre élévations au carré suffisent, chacune réduite modulo 3233 avant la suivante :

$65^2 = 4\,225 \equiv 992$, puis $992^2 = 984\,064 \equiv 1\,232$, puis $1\,232^2 = 1\,517\,824 \equiv 1\,547$, puis $1\,547^2 = 2\,393\,209 \equiv 789$. Donc $65^{16} \equiv 789 \ [3233]$.

Il ne reste qu'une multiplication : $789 \times 65 = 51\,285 = 15 \times 3233 + 2790$, d'où $65^{17} \equiv \mathbf{2790} \ [3233]$. Cinq opérations au total, et aucun nombre intermédiaire de plus de sept chiffres, alors que $65^{17}$ écrit en entier en compterait trente et un. Réduire à chaque étape est ce qui rend le calcul possible.

À calculer soi-même

L'arithmétique modulaire se vérifie par le calcul, et chaque étape tient sur une ligne. La faire une fois dispense de croire les formules sur parole.

Les deux dernières réponses donnent la mesure de l'exponentiation rapide sur un petit exposant. 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.

Où la démarche dérape

Une simplification parfaitement légitime sur les entiers, et fausse modulo un composé.

Exercices type

Pourquoi 1 n'est-il pas considéré comme un nombre premier ?

Parce que l'unicité de la décomposition en facteurs premiers en dépend. Si 1 était premier, $12$ s'écrirait $2^2 \times 3$, mais aussi $1 \times 2^2 \times 3$, et $1^{17} \times 2^2 \times 3$ : la décomposition cesserait d'être unique.

Ce n'est donc pas une convention arbitraire, c'est le prix à payer pour garder un théorème qui sert partout ailleurs.

Jusqu'où faut-il aller pour vérifier qu'un nombre $N$ est premier ?

Jusqu'à $\sqrt{N}$, et pas plus loin. Si $N$ admet un diviseur $d$ supérieur à $\sqrt{N}$, alors $N/d$ est un diviseur inférieur à $\sqrt{N}$, et il aurait déjà été trouvé.

Le gain est considérable : vérifier un nombre de six chiffres demande mille essais au lieu d'un million.

Un inverse modulaire existe-t-il toujours ?

Non. L'inverse de $a$ modulo $n$ existe si et seulement si $\operatorname{pgcd}(a, n) = 1$.

La raison se lit sur Bézout : cette condition équivaut à l'existence de $u$ et $v$ tels que $au + nv = 1$, ce qui donne exactement $au \equiv 1 \pmod n$. L'algorithme d'Euclide étendu ne fait donc pas que répondre oui ou non : il construit l'inverse.

Pourquoi réduire à chaque étape plutôt qu'à la fin ?

Parce que les congruences sont compatibles avec l'addition et la multiplication : réduire en cours de route donne le même résultat que réduire à la fin.

La différence est de taille des nombres manipulés. Calculer $7^{100}$ en entier produit un nombre de quatre-vingt-cinq chiffres ; le calculer modulo 11 en réduisant à chaque étape ne fait jamais dépasser deux chiffres.

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 : c'est ce qui rend le calcul faisable à la main.
4. Réduire à chaque étape dans un calcul modulaire. 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, procéder par carrés successifs en suivant l'écriture binaire de l'exposant.

Synthèse

• Division euclidienne : $a = bq + r$ avec $0 \leq r < |b|$, et ce couple est unique. Attention au signe du reste selon le langage employé.
• Euclide : $\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, a \bmod b)$, en $O(\log n)$. Sa version étendue donne $u$ et $v$ tels que $au + bv = \operatorname{pgcd}$.
• Bézout : $a$ et $b$ sont premiers entre eux si et seulement s'il existe $u$ et $v$ tels que $au + bv = 1$.
• Congruences : compatibles avec l'addition et la multiplication, donc on réduit à chaque étape.
• Un facteur ne se simplifie que s'il est premier avec le module. Sinon la congruence a plusieurs solutions.
• Modulo un composé, un produit de non-nuls peut être nul. Modulo un premier, jamais.
• 1 n'est pas premier : l'unicité de la décomposition en dépend.
• Crible d'Ératosthène : barrer les multiples à partir de $p^2$, s'arrêter à $\sqrt{N}$.
• Factoriser est difficile : constaté, pas démontré.
• $\varphi(p) = p - 1$ et $\varphi(pq) = (p-1)(q-1)$, jamais $\varphi(N) = N - 1$ pour un composé.
• Euler : $a^{\varphi(n)} \equiv 1 \pmod n$ dès que $\operatorname{pgcd}(a, n) = 1$.
• Exponentiation rapide : carrés successifs, $O(\log d)$ multiplications au lieu de $d$.

Et ensuite

Toute cette arithmétique a été construite pour servir, et elle sert à une chose précise : rendre facile dans un sens ce qui est impraticable dans l'autre. Cryptographie exploite cette asymétrie.