Théorie des nombres et arithmétique modulaire : exercices corrigés pas à pas

1Restes et congruences

Diviser a par n donne un quotient q et un reste r : a = q·n + r avec 0 ≤ r < n. Le reste se note a mod n. Pour un nombre négatif q est aussi négatif : −3 = −1·7 + 4, donc −3 mod 7 = 4.

Deux nombres sont congrus modulo n, a ≡ b (mod n), quand ils ont le même reste, c’est-à-dire quand n divise a − b.

On peut réduire les restes à chaque étape, ce qui garde les nombres petits :

Par exemple 47·58 mod 9 : 47 ≡ 2 et 58 ≡ 4, donc 47·58 ≡ 8 (mod 9).

2Algorithme d’Euclide

Le plus grand commun diviseur pgcd(a, b) est le plus grand nombre qui divise les deux. L’algorithme d’Euclide utilise pgcd(a, b) = pgcd(b, a mod b) :

1. Divisez : a = q·b + r.
2. Remplacez (a, b) par (b, r).
3. Répétez jusqu’à ce que le reste soit 0. Le dernier reste non nul est le pgcd.

Le plus petit commun multiple s’en déduit : ppcm(a, b) = a·b / pgcd(a, b).

3Inverses et algorithme étendu

L’inverse de a modulo n est le nombre x tel que a·x ≡ 1 (mod n). Il existe exactement quand pgcd(a, n) = 1.

L’algorithme d’Euclide étendu applique Euclide à (n, a) et garde un coefficient t pour chaque reste, de sorte que chaque reste r ≡ t·a (mod n). Commencez avec t = 0 pour n et t = 1 pour a ; chaque nouveau t est le t de deux lignes plus haut moins q fois le t d’une ligne plus haut. Quand le reste 1 apparaît, son t est l’inverse.

Avec l’inverse, une congruence a·x ≡ b (mod n) se résout par x ≡ a⁻¹·b. Quand d = pgcd(a, n) est supérieur à 1, il y a d solutions si d divise b, et aucune sinon.

Deux congruences à modules premiers entre eux, x ≡ r₁ (mod m₁) et x ≡ r₂ (mod m₂), ont exactement une solution modulo m₁·m₂ (théorème des restes chinois). Écrivez x = r₁ + m₁k et résolvez pour k.

4Puissances modulaires et RSA

Le carré répété calcule rapidement aᵏ mod n : écrivez k en binaire, trouvez a, a², a⁴, a⁸, … mod n en élevant au carré et en réduisant, et multipliez les puissances dont le bit vaut 1.

Petit théorème de Fermat : pour un nombre premier p qui ne divise pas a, aᵖ⁻¹ ≡ 1 (mod p). On peut donc réduire l’exposant modulo p − 1.

Le RSA construit une clé à partir de deux nombres premiers p et q :

1. n = p·q et φ(n) = (p − 1)(q − 1).
2. Choisissez e avec pgcd(e, φ(n)) = 1 ; (n, e) est la clé publique.
3. Calculez d = e⁻¹ mod φ(n) : la clé privée.
4. Chiffrer c = mᵉ mod n ; déchiffrer m = cᵈ mod n.

L’indicatrice d’Euler φ(n) compte les nombres de 1 à n premiers avec n : φ(p) = p − 1 pour un nombre premier, φ(pᵏ) = pᵏ − pᵏ⁻¹, et φ est multiplicative pour des facteurs premiers entre eux.

5Erreurs fréquentes

• Donner un reste négatif pour un nombre négatif : −17 mod 5 vaut 3, pas −2.
• S’arrêter dans Euclide au premier reste au lieu du dernier reste non nul.
• Oublier d’ajouter n à un coefficient négatif de l’algorithme étendu.
• Calculer l’exposant RSA d modulo n au lieu de modulo φ(n).
• Réduire un exposant modulo p au lieu de p − 1 avec le théorème de Fermat.

6À quoi ressemblent les questions d’examen

• Facile : pgcd et restes. Vous appliquez l’algorithme d’Euclide pour un pgcd ou un ppcm, trouvez les restes de nombres négatifs, et réduisez des sommes et des produits modulo n.
• Moyen : inverses et congruences. Vous trouvez des inverses modulaires avec l’algorithme étendu, résolvez des congruences linéaires, combinez deux congruences avec le théorème des restes chinois, et calculez φ(n) d’Euler.
• Difficile : puissances modulaires et RSA. Vous utilisez le carré répété et le théorème de Fermat, résolvez des congruences à plusieurs solutions, et trouvez des exposants privés RSA, des chiffrés et des messages déchiffrés.