Arithmétique modulaire
L'arithmétique modulaire, parfois appelée arithmétique des congruences, est une branche de la théorie des nombres étudiant les opérations arithmétiques effectuées sur les restes de la division entière. Plutôt que de manipuler directement des nombres pouvant devenir très grands, elle consiste à ne conserver que leur reste après division par un entier positif appelé module.
Cette discipline occupe une place essentielle en informatique. Elle intervient dans les générateurs de nombres pseudo-aléatoires, les fonctions de hachage, les sommes de contrôle (checksums), les calendriers, la cryptographie, les algorithmes de compression, les tables de hachage, les nombres premiers, les codes correcteurs d'erreurs, les systèmes distribués et de nombreux algorithmes numériques.
L'arithmétique modulaire présente également l'avantage de limiter naturellement la taille des valeurs manipulées, ce qui réduit les risques de dépassement de capacité tout en permettant la réalisation de calculs extrêmement rapides.
Division euclidienne
L'arithmétique modulaire repose sur la division euclidienne.
Pour deux entiers :
| a |
et
| n > 0 |
il existe deux entiers uniques :
| q |
et
| r |
tels que :
| a = qn + r |
avec :
| 0 ≤ r < n |
où :
- q représente le quotient ;
- r représente le reste.
Par exemple :
| 35 = 5 × 6 + 5 |
Le reste de la division de 35 par 6 est donc :
| 5 |
Définition du modulo
Le modulo correspond au reste de la division euclidienne.
On note généralement :
| a mod n |
Par exemple :
| 17 mod 5 = 2 |
car :
| 17 = 3 × 5 + 2 |
Autres exemples :
| 22 mod 8 = 6 |
| 100 mod 9 = 1 |
| 255 mod 16 = 15 |
Congruence
Deux nombres sont dits **congruents modulo n** lorsqu'ils possèdent le même reste.
On écrit :
| a ≡ b (mod n) |
Cette relation signifie que :
| a mod n = b mod n |
ou de manière équivalente :
| n divise (a-b) |
Exemple de congruence
Considérons :
| 17 |
et
| 2 |
On obtient :
| 17 mod 5 = 2 |
et
| 2 mod 5 = 2 |
Ainsi :
| 17 ≡ 2 (mod 5) |
De même :
| 32 ≡ 2 (mod 10) |
car les deux nombres se terminent par le même chiffre.
Classes de congruence
Tous les entiers ayant le même reste appartiennent à la même classe de congruence.
Modulo 4, les classes sont :
| [0] = {...,-8,-4,0,4,8,...} |
| [1] = {...,-7,-3,1,5,9,...} |
| [2] = {...,-6,-2,2,6,10,...} |
| [3] = {...,-5,-1,3,7,11,...} |
Chaque entier appartient exactement à une classe.
Représentant canonique
On choisit généralement comme représentant de chaque classe le reste compris entre :
| 0 |
et
| n-1 |
Ainsi, modulo 7, les représentants sont :
|
0 1 2 3 4 5 6 |
Toutes les opérations peuvent être effectuées uniquement sur ces représentants.
Addition modulaire
L'addition est réalisée normalement puis réduite modulo n.
| (a+b) mod n |
Exemple :
| 8 + 11 mod 5 |
donne :
| 19 mod 5 = 4 |
On peut également réduire avant le calcul :
| 8 mod 5 = 3 |
| 11 mod 5 = 1 |
Puis :
| 3 + 1 = 4 |
Soustraction modulaire
La soustraction est définie par :
| (a-b) mod n |
Exemple :
| 8-13 mod 7 |
donne :
| -5 mod 7 = 2 |
car :
| -5 ≡ 2 (mod 7) |
Multiplication modulaire
La multiplication suit le même principe.
| (a×b) mod n |
Par exemple :
| 12 × 9 mod 7 |
Calcul direct :
| 108 mod 7 = 3 |
Calcul réduit :
| 12 mod 7 = 5 |
| 9 mod 7 = 2 |
Puis :
| 5 × 2 = 10 |
| 10 mod 7 = 3 |
Les deux méthodes donnent le même résultat.
Propriétés fondamentales
Pour tout entier :
| a,b,c |
on obtient :
|
(a+b) mod n = ((a mod n)+(b mod n)) mod n |
|
(a-b) mod n = ((a mod n)-(b mod n)) mod n |
|
(ab) mod n = ((a mod n)(b mod n)) mod n |
Ces propriétés permettent de réduire les calculs intermédiaires.
Puissance modulaire
La puissance modulaire consiste à calculer :
| a^k mod n |
sans calculer entièrement :
| a^k |
Exemple :
| 3^20 mod 7 |
Plutôt que calculer :
| 3^20 |
on réduit les valeurs à chaque étape.
Cette opération est indispensable en cryptographie.
Exponentiation rapide
La méthode classique utilise l'algorithme de l'exponentiation rapide.
|
MODULE PuissanceModulaire(a,e,n) résultat ← 1 a ← a mod n TANT QUE e > 0 SI e est impair ALORS résultat ← (résultat × a) mod n FIN SI a ← (a × a) mod n e ← e DIV 2 FIN TANT QUE RETOURNER résultat |
Complexité :
| O(log e) |
Exemple
Calculons :
| 5^13 mod 23 |
L'algorithme effectue seulement quelques multiplications au lieu de calculer :
|
5^13 = 1220703125 |
Le résultat est :
| 21 |
Inverse modulaire
L'inverse modulaire d'un entier a est un entier :
| a-1 |
tel que :
| aa-1 ≡ 1 (mod n) |
Cet inverse n'existe que lorsque :
| PGCD(a,n)=1 |
Exemple
Modulo :
| 11 |
L'inverse de :
| 7 |
est :
| 8 |
car :
| 7×8=56 |
et :
| 56 mod 11 =1 |
Calcul par l'algorithme d'Euclide étendu
L'inverse modulaire est généralement obtenu grâce à l'algorithme d'Euclide étendu.
Cet algorithme calcule simultanément :
- le PGCD ;
- les coefficients de Bézout.
Il est largement utilisé dans RSA et ECC.
Complexité :
| O(log n) |
Division modulaire
La division n'est pas directement définie.
On effectue :
| a/b |
en calculant :
| a×b-1 |
Exemple :
| 8/3 mod 11 |
Inverse de 3 :
| 4 |
car :
| 3×4=12≡1 |
Donc :
| 8×4 mod 11=10 |
Petit théorème de Fermat
Si :
| p |
est premier et :
| a |
non divisible par :
| p |
alors :
|
a^(p?1) ≡1 (mod p) |
Il permet notamment de calculer rapidement un inverse :
|
a-1 = a^(p-2) (mod p) |
Théorème d'Euler
Le théorème d'Euler généralise celui de Fermat.
Si :
| PGCD(a,n)=1 |
alors :
|
a^φ(n) ≡1 (mod n) |
où :
| φ(n) |
désigne la fonction indicatrice d'Euler.
Fonction indicatrice d'Euler
La fonction :
| φ(n) |
compte les entiers positifs inférieurs ou égaux à :
| n |
qui sont premiers avec :
| n |
Par exemple :
| φ(9)=6 |
car :
| 1,2,4,5,7,8 |
sont premiers avec 9.
Théorème chinois des restes
Le théorème chinois des restes permet de résoudre simultanément plusieurs congruences.
Exemple :
| x≡2(mod 3) |
| x≡3(mod 5) |
| x≡2(mod 7) |
La solution est :
| 23 |
Modulo :
| 105 |
Ce théorème est très utilisé dans RSA.
Calcul modulo une puissance de deux
Lorsque le module est une puissance de deux :
| 2^k |
le calcul du modulo peut être remplacé par un masque binaire.
Exemple :
| x mod 16 |
équivaut à :
| x AND 15 |
Cette technique est extrêmement rapide.
Nombres négatifs
La représentation des nombres négatifs dépend du langage.
Mathématiquement :
| -3 mod 7 = 4 |
Cependant certains langages retournent :
| -3 |
Il convient donc de vérifier le comportement de l'opérateur `%`.
Algorithme naïf du modulo
|
MODULE Modulo(a,n) TANT QUE a ≥ n a ← a-n FIN TANT QUE RETOURNER a |
Cette méthode est simple mais inefficace.
Complexité :
| O(a/n) |
Algorithme utilisant la division
|
MODULE Modulo(a,n) q ← a DIV n RETOURNER a-q×n |
Complexité :
| O(1) |
sur les processeurs modernes.
Exemple Java
- public class ModularArithmetic {
-
- public static long powerMod(
- long base,
- long exponent,
- long modulus) {
-
- long result = 1;
-
- base %= modulus;
-
- while (exponent > 0) {
-
- if ((exponent & 1) == 1)
- result =
- (result * base)
- % modulus;
-
- base =
- (base * base)
- % modulus;
-
- exponent >>= 1;
- }
-
- return result;
- }
-
- public static void main(String[] args) {
-
- System.out.println(
- powerMod(5,13,23)
- );
- }
-
- }
Applications
L'arithmétique modulaire est utilisée dans :
- RSA ;
- Diffie-Hellman ;
- courbes elliptiques ;
- fonctions de hachage ;
- CRC ;
- générateurs pseudo-aléatoires ;
- horloges ;
- calendriers ;
- anneaux circulaires ;
- buffers circulaires ;
- algorithmes de chiffrement ;
- codage correcteur d'erreurs ;
- blockchain ;
- calcul scientifique.
Avantages
L'arithmétique modulaire présente de nombreux avantages :
- elle limite naturellement la taille des nombres ;
- elle réduit les risques de dépassement de capacité ;
- elle accélère les calculs ;
- elle simplifie de nombreuses démonstrations ;
- elle constitue la base de la cryptographie moderne ;
- elle permet des algorithmes très efficaces ;
- elle est parfaitement adaptée aux architectures binaires.
Limites et précautions
Plusieurs précautions doivent être prises :
- tous les entiers ne possèdent pas d'inverse modulaire ;
- la division modulaire exige l'existence d'un inverse ;
- le comportement du modulo négatif varie selon les langages ;
- certains calculs intermédiaires peuvent provoquer un dépassement avant la réduction ;
- les modules non premiers possèdent des propriétés plus complexes ;
- certaines optimisations ne sont valables que pour des modules particuliers.
Remarque
L'arithmétique modulaire constitue l'un des fondements des mathématiques discrètes et de l'informatique moderne. En remplaçant les nombres par leurs classes de congruence, elle permet d'effectuer des calculs rapides, fiables et adaptés aux contraintes des ordinateurs. Son utilisation est omniprésente dans les compilateurs, les systèmes d'exploitation, les protocoles de sécurité, les bases de données, les réseaux, les algorithmes de recherche et les systèmes cryptographiques, où elle permet de manipuler efficacement des nombres très grands tout en conservant des propriétés mathématiques remarquables.