L'essentiel à connaître
Deux entiers $a$ et $b$ sont congrus modulo $n$ quand $n$ divise $a - b$ : on écrit $a \equiv b\ [n]$, ou $a \equiv b \pmod{n}$. Par exemple, $17 \equiv 2\ [5]$ car $17 - 2 = 15 = 3 \times 5$. Tout entier, même négatif, est congru à un seul reste $r$ tel que $0 \leqslant r \leqslant n - 1$ : celui de sa division euclidienne par $n$. Ainsi $-1 \equiv 9\ [10]$, et le dernier chiffre d'un entier est son reste modulo $10$.
Les congruences s'additionnent, se multiplient et s'élèvent à une puissance membre à membre. Tu réduis donc avant de calculer : $10 \equiv 1\ [9]$ donne $10^{100} \equiv 1\ [9]$. Dès que $a^k \equiv 1\ [n]$, les puissances de $a$ tournent en boucle et l'exposant se réduit modulo $k$.
Le pgcd (plus grand commun diviseur) se calcule par l'algorithme d'Euclide : tu remplaces $(a, b)$ par $(b, r)$, où $r$ est le reste de la division de $a$ par $b$, jusqu'à tomber sur un reste nul. Le pgcd est le dernier reste non nul. En remontant les divisions, tu obtiens une relation de Bézout $au + nv = \mathrm{pgcd}(a, n)$. Un inverse de $a$ modulo $n$ est un entier $u$ tel que $au \equiv 1\ [n]$ : il existe si et seulement si $\mathrm{pgcd}(a, n) = 1$, et c'est le coefficient $u$ de la relation $au + nv = 1$.
Propriétés : si $p$ est premier et ne divise pas $a$, alors $a^{p-1} \equiv 1\ [p]$ (petit théorème de Fermat). Si $\mathrm{pgcd}(m, n) = 1$, le système $x \equiv a\ [m]$ et $x \equiv b\ [n]$ a une solution, unique modulo $mn$ (théorème chinois).
Piège classique : une congruence ne se simplifie pas comme une égalité. De $ka \equiv kb\ [n]$, tu tires seulement $a \equiv b\ [n/g]$, avec $g = \mathrm{pgcd}(k, n)$ : $2 \times 4 \equiv 2 \times 1\ [6]$, mais $4 \not\equiv 1\ [6]$. De même, avec Fermat, un exposant se réduit modulo $p - 1$, jamais modulo $p$.
Le chiffrement RSA, publié par Rivest, Shamir et Adleman en 1978, assemble ces outils. On choisit deux grands nombres premiers distincts $p$ et $q$, on pose $n = pq$ et $\varphi(n) = (p-1)(q-1)$, le nombre d'entiers de $1$ à $n$ premiers avec $n$. La clé publique est $(n, e)$, avec $\mathrm{pgcd}(e, \varphi(n)) = 1$ ; la clé privée $d$ est l'inverse de $e$ modulo $\varphi(n)$. Chiffrer est rapide (on élève au carré en réduisant modulo $n$ à chaque étape), mais calculer $d$ demande $\varphi(n)$, et connaître $\varphi(n)$ revient à connaître $p$ et $q$ : la sécurité repose sur la difficulté de factoriser $n$.
Formule : pour un message $m$ tel que $0 \leqslant m \leqslant n - 1$, on chiffre $c \equiv m^e\ [n]$ et on déchiffre $m \equiv c^d\ [n]$, où $ed \equiv 1\ [\varphi(n)]$.
Quiz : teste tes connaissances
Les questions montent en difficulté : les trois dernières sont les plus piégeuses.
Question 1 : Quel est le reste de la division euclidienne de $38$ par $7$ ?
Réponse : B. $38 = 7 \times 5 + 3$ avec $0 \leqslant 3 \leqslant 6$, donc $38 \equiv 3\ [7]$. Le piège $5$ est le quotient, pas le reste ; quant à $4$, il vient de $38 - 42 = -4$ avec le signe oublié.
Question 2 : On sait que $a \equiv 5\ [8]$. Quel est le reste de $a^2$ modulo $8$ ?
Réponse : D. En élevant au carré, $a^2 \equiv 25\ [8]$, et $25 = 3 \times 8 + 1$, donc le reste vaut $1$. Le piège $3$ est le quotient de $25$ par $8$ ; $2$ vient de $2 \times 5$, un double au lieu d'un carré.
Question 3 : Que vaut $\mathrm{pgcd}(252, 198)$ ?
Réponse : A. $252 = 198 \times 1 + 54$, puis $198 = 54 \times 3 + 36$, $54 = 36 \times 1 + 18$ et $36 = 18 \times 2 + 0$ : le dernier reste non nul est $18$. Le piège $36$ est l'avant-dernier reste : on s'est arrêté une division trop tôt.
Question 4 : Sur quoi repose la sécurité de RSA ?
Réponse : C. Tout le monde connaît $(n, e)$, mais calculer $d$ demande $\varphi(n)$, donc la factorisation de $n$ ; l'ANSSI impose ainsi un module d'au moins 2048 bits pour un usage jusqu'à fin 2030, et de 3072 bits à partir de 2031. Le piège A est faux : par carrés successifs, $m^e$ modulo $n$ coûte au plus deux multiplications par chiffre binaire de $e$.
Question 5 : Lequel de ces entiers a un inverse modulo $12$ ?
Réponse : A. $\mathrm{pgcd}(5, 12) = 1$, et en effet $5 \times 5 = 25 \equiv 1\ [12]$. Le piège $3$ est premier, mais pas premier avec $12$ : $3u$ est toujours congru à $0$, $3$, $6$ ou $9$ modulo $12$, jamais à $1$.
Question 6 : L'algorithme d'Euclide étendu donne $3 \times 26 - 11 \times 7 = 1$. Quel est l'inverse de $7$ modulo $26$, entre $0$ et $25$ ?
Réponse : D. Modulo $26$, le terme $3 \times 26$ disparaît : $7 \times (-11) \equiv 1\ [26]$, et $-11 \equiv 15\ [26]$. On vérifie : $7 \times 15 = 105 = 4 \times 26 + 1$. Le piège $11$ oublie le signe moins : $7 \times 11 = 77 \equiv -1\ [26]$.
Question 7 : Quel est le dernier chiffre de $7^{50}$ ?
Réponse : C. Modulo $10$, les puissances de $7$ valent $7$, $9$, $3$, $1$, puis recommencent, car $7^4 = 2401 \equiv 1\ [10]$. Comme $50 = 4 \times 12 + 2$, $7^{50} \equiv 7^2 = 49 \equiv 9\ [10]$. Le piège $1$ réduit l'exposant modulo $10$, alors que c'est la longueur du cycle, $4$, qui compte.
Question 8 : Quelles sont les solutions du système $x \equiv 2\ [3]$ et $x \equiv 3\ [5]$ ?
Réponse : B. Les entiers de $0$ à $14$ congrus à $3$ modulo $5$ sont $3$, $8$ et $13$ ; seul $8$ laisse le reste $2$ modulo $3$. Comme $\mathrm{pgcd}(3, 5) = 1$, la solution est unique modulo $15$. Le piège $5$ additionne les restes, mais $5 \equiv 0\ [5]$.
Question 9 : Une clé RSA d'exemple, minuscule pour le calcul à la main, a pour clé publique $(n, e) = (33, 3)$ et pour clé privée $d = 7$. Quel est le chiffré $c$ du message $m = 4$, entre $0$ et $32$ ?
Réponse : D. On calcule $4^3 = 64 = 1 \times 33 + 31$, donc $c = 31$. Le piège $16$ utilise la clé privée : $4^7 \equiv 16\ [33]$, alors qu'on chiffre avec $e$.
Question 10 : Quel est le reste de la division euclidienne de $-17$ par $5$ ?
Réponse : A. $-17 = 5 \times (-4) + 3$ avec $0 \leqslant 3 \leqslant 4$. Le piège $-2$ vient de $-17 = 5 \times (-3) - 2$ : l'égalité est juste, mais un reste de division euclidienne n'est jamais négatif.
Question 11 : Avec la même clé ($n = 33$, $d = 7$), tu reçois $c = 31$. Quel message $m$ retrouves-tu ?
Réponse : C. Comme $31 \equiv -2\ [33]$, on a $31^7 \equiv (-2)^7 = -128$, et $-128 + 4 \times 33 = 4$ : c'est bien le message de la question 9. Le piège $29$ perd le signe : $128 \equiv 29\ [33]$, qui est l'opposé de $4$.
Question 12 : Pour une clé RSA, on connaît $n = pq = 77$ et $\varphi(n) = 60$. De quel polynôme $p$ et $q$ sont-ils les racines ?
Réponse : B. $\varphi(n) = (p-1)(q-1) = pq - (p + q) + 1$, donc $p + q = 77 - 60 + 1 = 18$, et $p$, $q$ sont les racines de $X^2 - 18X + 77 = (X - 7)(X - 11)$. Connaître $\varphi(n)$ suffit donc pour factoriser $n$. Le piège A oublie le $+1$ du développement.
Question 13 : Quel est le reste de $3^{100}$ modulo $7$ ?
Réponse : A. $7$ est premier et ne divise pas $3$, donc $3^6 \equiv 1\ [7]$ : l'exposant se réduit modulo $6$. Comme $100 = 6 \times 16 + 4$, $3^{100} \equiv 3^4 = 81 \equiv 4\ [7]$. Le piège $2$ réduit l'exposant modulo $7$ : $100 \equiv 2\ [7]$, puis $3^2 = 9 \equiv 2\ [7]$.
Question 14 : Combien d'entiers $x$ entre $0$ et $14$ vérifient $10x \equiv 10\ [15]$ ?
Réponse : C. $15$ divise $10(x - 1)$ si et seulement si $3$ divise $2(x - 1)$, soit $x \equiv 1\ [3]$ : on simplifie par $10$ en divisant le modulo par $\mathrm{pgcd}(10, 15) = 5$. Le piège A simplifie comme dans une égalité, or $10 \times 4 = 40 \equiv 10\ [15]$ alors que $4 \not\equiv 1\ [15]$.
Question 15 : Une clé RSA d'exemple part de $p = 5$ et $q = 11$, donc $n = 55$, avec $e = 7$. Quelle est la plus petite clé privée $d$ positive ?
Réponse : D. $d$ est l'inverse de $7$ modulo $\varphi(55) = 4 \times 10 = 40$ : $7 \times 23 = 161 = 4 \times 40 + 1$. Le piège $8$ est l'inverse de $7$ modulo $n$ ($7 \times 8 = 56$) : il ne redonne pas le message en général, car le déchiffrement demande $ed \equiv 1\ [\varphi(n)]$.
Sources
ANSSI, Règles et recommandations concernant le choix et le dimensionnement des mécanismes cryptographiques, version 3.00 du 20 mars 2026, partie 2.2.1.1 (factorisation).
R. L. Rivest, A. Shamir et L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, vol. 21, n° 2, 1978, p. 120-126.