🔢
Les bases de l'arithmétique modulaireL'arithmétique modulaire consiste à travailler avec les restes de la division euclidienne. Deux entiers a et b sont congrus modulo n s'ils ont le même reste dans la division par n. Par exemple, 17 et 5 sont congrus modulo 12 car 17 = 1×12 + 5. Cette notion est naturelle avec une horloge : après 12 heures, on revient à 0. En terminale, on note a ≡ b [n] et on dit que n divise la différence a − b.
📢 Rappel
Division euclidienne : pour a entier et b entier naturel non nul, il existe un unique couple (q, r) avec a = bq + r et 0 ≤ r < b.
📖 Définition
Congruence : a ≡ b [n] signifie que a et b ont le même reste dans la division par n.
🔍 Exemple
Sur une horloge, 14 h et 2 h sont congrus modulo 12 : 14 ≡ 2 [12].
💡 À retenir : Deux nombres sont congrus modulo n s'ils diffèrent d'un multiple de n.
➕
Calculer modulo nLes congruences se comportent bien avec l'addition et la multiplication : si a ≡ b [n] et c ≡ d [n], alors a+c ≡ b+d [n] et a×c ≡ b×d [n]. Cela permet de simplifier les calculs en remplaçant chaque nombre par son reste. Pour les puissances, on peut réduire la base modulo n avant de calculer. Par exemple, pour trouver le chiffre des unités de 7^4, on travaille modulo 10 : 7 ≡ 7 [10], 7^2 ≡ 49 ≡ 9 [10], donc 7^4 ≡ 9^2 ≡ 81 ≡ 1 [10].
⭐ À retenir
Si a ≡ b [n] et c ≡ d [n], alors a+c ≡ b+d [n] et ac ≡ bd [n].
🔍 Exemple
Modulo 10, 27 ≡ 7, donc 27^2 ≡ 7^2 ≡ 49 ≡ 9 [10].
💡 À retenir : On peut additionner, multiplier et élever à une puissance en réduisant modulo n à chaque étape.
🔑
Coder et décoderLe chiffrement affine code une lettre par un nombre x entre 0 et 25, puis applique la fonction y ≡ ax + b [26]. Pour décoder, il faut inverser cette fonction, donc trouver un entier a^{-1} tel que a×a^{-1} ≡ 1 [26]. Cet inverse n'existe que si a et 26 sont premiers entre eux. Par exemple, avec a = 5 et b = 8, la lettre C (x = 2) devient y ≡ 5×2 + 8 ≡ 18 [26], soit la lettre S. Pour décoder, on utilise x ≡ a^{-1}(y − b) [26].
📖 Définition
Inverse modulaire : a^{-1} modulo n est un entier u tel que a×u ≡ 1 [n].
🔍 Exemple
5×21 = 105 = 4×26 + 1, donc 21 est l'inverse de 5 modulo 26.
📢 Rappel
Deux nombres sont premiers entre eux si leur PGCD vaut 1.
💡 À retenir : Le décodage repose sur l'inverse modulaire de a modulo 26.
🔐
Cryptographie moderneLe système RSA, utilisé pour sécuriser les transactions en ligne, repose sur la difficulté de factoriser un grand nombre en produit de deux nombres premiers. On choisit deux grands nombres premiers p et q, puis on calcule n = p×q et φ(n) = (p−1)(q−1). La clé publique contient n et un exposant e premier avec φ(n). La clé privée est l'inverse de e modulo φ(n). Coder un message M consiste à calculer C ≡ M^e [n] ; décoder nécessite la clé privée d pour calculer M ≡ C^d [n].
📢 Rappel
Un nombre premier n'a que deux diviseurs : 1 et lui-même.
⭐ À retenir
La clé privée RSA est l'inverse de e modulo (p−1)(q−1).
🔍 Exemple
Avec p=3, q=11, n=33, φ(n)=20 ; si e=7, alors d=3 car 7×3=21 ≡ 1 [20].
💡 À retenir : La sécurité du RSA vient de la difficulté pratique de factoriser n en p×q.