Congruences modulaires

On dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \pmod{n}$, si $n \mid (a - b)$.

Compatibilité avec les opérations : si $a \equiv a'$ et $b \equiv b' \pmod{n}$, alors : $a + b \equiv a' + b' \pmod{n} \qquad a \times b \equiv a' \times b' \pmod{n} \qquad a^k \equiv a'^k \pmod{n}$

Anneau $\mathbb{Z}/n\mathbb{Z}$ : les classes $\{[0],[1],\ldots,[n-1]\}$ forment un anneau avec addition et multiplication modulo $n$.

Inversibilité : $[a]$ est inversible dans $\mathbb{Z}/n\mathbb{Z}$ si et seulement si $\gcd(a,n) = 1$.

Si $n = p$ est premier, tous les éléments non nuls sont inversibles : $\mathbb{Z}/p\mathbb{Z}$ est un corps.

Petit théorème de Fermat : si $p$ premier et $\gcd(a,p) = 1$, alors $a^{p-1} \equiv 1 \pmod{p}$.

Théorème d'Euler : si $\gcd(a,n) = 1$, alors $a^{\phi(n)} \equiv 1 \pmod{n}$, avec $\phi(pq) = (p-1)(q-1)$ pour $p, q$ premiers distincts.

Inverse via Fermat (si $p$ premier) : $a^{-1} \equiv a^{p-2} \pmod{p}$.

Théorème chinois des restes (CRT) : Si $n_1, \ldots, n_k$ sont deux à deux premiers entre eux, alors le système : $\begin{cases} x \equiv a_1 \pmod{n_1} \\ \vdots \\ x \equiv a_k \pmod{n_k} \end{cases}$ admet une solution unique modulo $N = n_1 \cdots n_k$.

Construction : Pour chaque $i$, on pose $N_i = N/n_i$ et $M_i = N_i^{-1} \bmod n_i$. La solution est : $x \equiv \sum_{i=1}^k a_i N_i M_i \pmod{N}$

Interprétation algébrique : Le CRT établit l'isomorphisme : $\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$

Un entier est entièrement déterminé par ses restes modulo des modules premiers entre eux.

Génération des clés RSA :

1. Choisir deux grands premiers $p$ et $q$, poser $n = pq$
2. Calculer $\phi(n) = (p-1)(q-1)$
3. Choisir $e$ tel que $\gcd(e, \phi(n)) = 1$ (souvent $e = 65537$)
4. Calculer $d = e^{-1} \bmod \phi(n)$ via l'algorithme d'Euclide étendu

Chiffrement : $c \equiv m^e \pmod{n}$ — Déchiffrement : $m \equiv c^d \pmod{n}$

Pourquoi ça marche : $ed \equiv 1 \pmod{\phi(n)}$, donc $c^d = m^{ed} = m^{1+k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \pmod n$ par Euler.

Sécurité : repose sur la difficulté de factoriser $n = pq$ pour des grands premiers (2048 bits en pratique). Sans $p$ et $q$, impossible de calculer $\phi(n)$ et donc $d$.

Tests de primalité :

• Test de Fermat : si $a^{n-1} \not\equiv 1 \pmod n$, alors $n$ est composé. Si $\equiv 1$, probablement premier. Faille : nombres de Carmichael (ex. $561 = 3 \times 11 \times 17$) passent le test mais sont composés.
• Test de Miller-Rabin : variante probabiliste plus robuste, utilisée en pratique.
• Test AKS (2002) : premier test déterministe polynomial en temps.

Ordre d'un élément modulo $n$ :

L'ordre de $a$ dans $(\mathbb{Z}/n\mathbb{Z})^*$ est le plus petit entier $k \geq 1$ tel que $a^k \equiv 1 \pmod{n}$, noté $\text{ord}_n(a)$.

L'ordre divise toujours $\phi(n)$ (conséquence du théorème de Lagrange).

Si $\text{ord}_n(a) = \phi(n)$, alors $a$ est un générateur (racine primitive) de $(\mathbb{Z}/n\mathbb{Z})^*$.

Critères de divisibilité via congruences :

| Diviseur | Condition | Raison ($10 \equiv ? \pmod{d}$) | |---|---|---| | $2$ | Dernier chiffre pair | $10 \equiv 0 \pmod 2$ | | $5$ | Dernier chiffre $\in \{0,5\}$ | $10 \equiv 0 \pmod 5$ | | $3$ | Somme des chiffres $\equiv 0 \pmod 3$ | $10 \equiv 1 \pmod 3$ | | $9$ | Somme des chiffres $\equiv 0 \pmod 9$ | $10 \equiv 1 \pmod 9$ | | $11$ | Somme alternée $\equiv 0 \pmod{11}$ | $10 \equiv -1 \pmod{11}$ |

Preuve du critère pour 3 : si $N = a_k 10^k + \cdots + a_1 10 + a_0$, alors comme $10 \equiv 1 \pmod 3$, on a $10^i \equiv 1 \pmod 3$ pour tout $i$, donc $N \equiv a_k + \cdots + a_0 \pmod 3$.

Critère pour 11 : comme $10 \equiv -1 \pmod{11}$, on a $10^i \equiv (-1)^i \pmod{11}$, d'où $N \equiv a_0 - a_1 + a_2 - a_3 + \cdots \pmod{11}$.

Application en hachage : dans une table de hachage de taille $n$ première, l'indice de clé $k$ est $k \bmod n$. Choisir $n$ premier garantit que l'ordre de chaque base est maximal, minimisant les collisions par sondage linéaire.