Arithmétique modulaire
Guide
La première partie de ce document est une introduction de l'anneau
/
à partir des congruences.
La deuxième partie met l'accent sur quelques résolutions de problèmes
où l'utilisation des congruences est fondamentale ou simplement pratique.
Ce document n'a aucune prétention à être complet ni même achevé. On espère qu'il
peut être utile ainsi.
Définition et opérations algébriques
Définition
Une
classe de congruence modulo
est un sous-ensemble de
de la forme
avec
un entier.
L'ensemble des classes de congruences modulo
est noté
. On note aussi
=
mod
Un entier
est appelé un
représentant de la
classe
si
et
sont congrus modulo
.
Exemple :
-
Les classes 33 + 97 et 518 + 97 sont égales.
-
Les classes 33 + 97 et 134 + 97 sont différentes.
-
L'entier
est un représentant de la classe 33 mod 97.
On choisit en général les représentants entre 0 et
, ce qui est toujours
possible.
Le reste de la division euclidienne de
par
est
bien un représentant de
mod
qui est compris entre 0 et
.
Mais il est quelquefois commode de prendre les représentants entre
et
et même de les prendre quelconques.
Exercice :
Classes
Exemple pour plus tard : Il est quand même
plus facile de calculer la puissance
-ième de la classe 126 mod 127 en utilisant
le représentant de cette classe qu'est -1. Ainsi :
mod 127
mod 127
Opérations
On définit les
opérations algébriques d'addition,
soustraction, multiplication par
Mais nous écrirons souvent
mod
, par exemple
14 + 35 mod 49 = 0 mod 49 , 14
35 mod 49 = 0 mod 49
et même
14 + 35
0 mod 49 , 14
35
0 mod 49 .
Théorème : /
est un anneau commutatif.
Exercices :
Opérations
,
Carrés
Somme et produit
Table d'addition
Voici la table d'addition dans
/8
:
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 |
2 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 |
3 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
4 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 |
5 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 |
6 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 |
7 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Table de multiplication
Voici la table de multiplication dans
/4
:
| 0 | 1 | 2 | 3 |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 2 | 3 |
2 | 0 | 2 | 0 | 2 |
3 | 0 | 3 | 2 | 1 |
Les zéros ont été mis en rouge. Pouvez-vous comparer le nombre de zéros avec le nombre de facteurs premiers de 4 ?
Inverses et diviseurs de zéro
Existence d'un inverse pour la multiplication
Théorème :
Soit un entier
premier à
.
Alors
est inversible dans
/
, c'est-à-dire qu'il existe
tel que
1 mod
.
En fait, il s'agit d'une
équivalence :
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
La démonstration donne aussi un moyen de
calcul de cet inverse.
L'entier
est premier avec
si et seulement s'il existe
et
dans
tels que
Donc,
- si
est premier avec
, il existe un entier
tel que
mod
et
est inversible dans /
.
- Si
est inversible dans /
, il existe un entier
tel que
.
Par définition de la congruence, cela signifie qu'il existe un entier
tel que
et on a
, donc
et
sont premiers entre eux.
Exercice :
Inverse :
1
2
3
Division :
I
II
III
Exemples
Exemple: Prenons
:
a=0 |
|
a=1 |
|
a=2 |
|
a=3 |
|
a=4 |
|
a=5 |
|
a=6 |
|
a=7 |
|
Lorsque
n'a pas d'inverse, on voit qu'il est alors
diviseur de zéro,
c'est-à-dire que
pour un entier
.
Exemple :
Pour
a=0 |
| a=4 |
|
a=1 |
|
a=5 |
|
a=2 |
| a=6 |
|
a=3 |
|
a=7 |
|
Cas où n est premier
Théorème.
Si
est un nombre premier, tout nombre non nul dans
a un inverse.
Démonstration
Comme
est premier, il est premier avec tout nombre qu'il ne divise pas,
c'est-à-dire avec tout nombre dont la classe de congruence modulo
n'est pas nul.
On applique alors le
théorème.
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
Exercices :
Puissance
Calcul de puissances :
I
II
Diviseurs de 0
Lorsque
n'a pas d'inverse, on voit qu'il est alors
diviseur de zéro, c'est-à-dire que
0 mod
pour un entier
.
Proposition :
Dans
/
,
est un diviseur de zéro si et seulement si
n'est pas premier avec
.
Démonstration.
-
Si
est diviseur de zéro, il n'est pas inversible donc d'après le
théorème,
Théorème : Soit un entier
. Alors
est inversible dans
si et seulement si
est premier à
.
il n'est pas premier avec
.
-
Si
n'est pas premier avec
, soit
le pgcd de
et de
.
Soit
le quotient de
par
; on a
,
et
.
Donc
mod
. La classe de
modulo
est non nulle, car
est un diviseur strict de
.
Exercice :
Diviseurs de zéro
1
2
3
Résolution de quelques problèmes
Résolution de l'équation linéaire a x = b mod n
La question est de trouver tous les entiers
vérifiant l'équation
mod
On peut adopter plusieurs points de vue selon qu'on est à l'aise
ou non dans l'anneau
/
.
Première étape :
L'équation
mod
a une solution
si et seulement si le pgcd
de
et de
divise
.
Dans ce cas, on divise l'équation par
(y compris
)
et on est ramené au cas où
et
sont premiers entre eux.
Deuxième étape :
-
Première méthode : travailler dans Z
il s'agit de trouver les entiers
tels qu'il existe
un entier
vérifiant
ou encore
On s'est donc ramené à résoudre une équation de Bezout. Elle a une solution
car on a supposé que
et
sont premiers entre eux.
-
Deuxième méthode : travailler dans Z/nZ
Comme
et
sont premiers entre eux, il existe
et
tel que
. En particulier, il existe un entier
tel que
1 mod
. On multiplie l'équation
mod
par
,
ce qui donne
mod
et donc comme
1 mod
mod
et on a résolu le problème.
On se rend compte qu'en fait il s'agit de la démonstration de ce que
est inversible dans /
et que si
,
mod
est l'inverse de
mod
dans /
.
L'avantage sur la première méthode : on n'a pas besoin de demander
l'existence de
tel que ... Il est caché dans
le
mod
: on se souvient que
mod
signifie en fait
.
Exercices rapides :
Equation linéaire modulaire
Exercice :
Equation linéaire
Petit théorème de Fermat
Théorème
Soit
un nombre premier impair. Alors pour tout entier
,
mod
.
On en déduit le
théorème de Fermat :
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,
1 mod
.
Théorème
Soit
un nombre premier impair. Soit
un entier premier à
. Alors,
-
il existe un plus petit entier
tel que
1 mod
cet entier est un diviseur de
;
- les entiers
vérifiant
1 mod
sont exactement les multiples de
.
Par le petit théorème de Fermat, l'ensemble des entiers
strictement positifs vérifiant
1 mod
est non vide
car il contient
. Il admet donc un plus petit élément. Notons-le
.
Faisons la division euclidienne de
par
:
avec
entier positif
. On a
mod
d'où
1
mod
Donc, par minimalité de
,
est soit plus grand que
, soit nul.
Donc
est nul, et
divise
.
Résolution d'équations du type a^b=c mod n
Il faut quand même préciser qui est l'inconnue ! Cela peut être
ou
.
On prend
un nombre premier.
-
Les équations du type
1 mod
peuvent être traitées en utilisant
le
Théorème de Fermat
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,
1 mod
.
et ses conséquences :
Les solutions de cette équation sont les multiples d'un diviseur de
à trouver.
On prend donc tous les diviseurs de
et on les essaye !
(on peut quand même réfléchir au moyen de ne pas faire trop de calculs :
si
n'est pas congru à 1 modulo
, pas la peine d'essayer
ou
).
-
Les équations du type
mod
avec
premier
à
et
premier à
: on va utiliser là encore le fait que
1 mod
. Pour cela, comme
et
sont premiers entre eux, on calcule l'identité de Bezout associée :
On a
mod
et on a résolu l'équation.
Exercice :
Equation multiplicative
Exercice :
Equation multiplicative II
Equation diophantienne linéaire à 3 inconnues
Soient
,
,
et
quatre entiers. On désire résoudre l'équation
en entiers. Les étapes de résolution peuvent être les suivantes :
-
Etape 1 : se ramener au cas où
sont premiers entre eux :
Explication
On commence par calculer le pgcd
des entiers
.
L'équation a une solution si et seulement si
divise
.
Dans ce cas, on peut diviser tous les coefficients par cet entier,
ce qui nous ramène au cas où ce pgcd est 1.
-
Etape 2 : Lorsque
,
,
sont premiers entre eux, on se ramène
au cas où deux des coefficients sont premiers entre eux :
Explication
Soit
le pgcd de
et
. On pose
,
avec
et
premiers entre eux.
Si
est une solution de l'équation, on a
mod
.
Comme
et
sont premiers entre eux, il existe un entier
tel que
1 mod
et la congruence est équivalente à
mod
Ainsi, si on choisit
un représentant de
mod
, on a
mod
et
avec
.
On pose
avec
.
L'équation devient
c'est-à-dire
avec maintenant
et
premiers entre eux.
-
Etape 3 :
Supposons
et
premiers entre eux. On cherche (et trouve) une solution
particulière avec
, ce qui revient à résoudre l'équation
:
Explication
Pour cela, on calcule des entiers
et
tels que
par l'algorithme d'Euclide.
Une solution particulière est alors donnée par
.
-
Etape 4 : Supposons
et
premiers entre eux.
On cherche les solutions de l'équation
.
Explication
L'équation est équivalente à
La discussion dans le cas de deux variables (en considérant
comme fixé)
implique que si
et
sont des entiers tels que
,
et
s'écrivent sous la forme
c'est-à-dire matriciellement
-
Etape 5 : Supposons
et
premiers entre eux et
. La solution générale de l'équation
est donnée
de manière matricielle par :
avec
et
appartenant à .
Une équation diophantienne non linéaire sans solution
On désire montrer que
l'équation
n'a pas de solutions entières.
- Soit
un
nombre premier impair. Montrer que si l'équation
0 mod
a une solution, alors
est congru à 1 mod 4.
Solution
Ici,
est impair, donc
est divisible par 2.
Si -1
mod
, alors
La dernière congruence est le petit
théorème de Fermat.
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,
1 mod
.
Donc
est pair,
ce qui signifie que
1 mod 4.
-
Supposons qu'il existe des entiers
et
tels
que
.
-
Montrer que
est impair.
Solution
Si
est pair,
7 mod 8, ce qui est impossible
car tout carré est pair ou congru à 1 mod 8.
-
Montrer que le produit d'entiers congrus à 1 mod 4 est
congru à 1 mod 4.
Solution
Si les nombres
sont congrus à
1 mod 4, on a
1 ... 1 = 1 mod 4.
-
Factoriser
sous la forme
. Montrer qu'il existe
un nombre premier
congru à 3 mod 4 divisant
. En déduire qu'il
existe un nombre premier congru à 3 mod 4 et divisant
.
Solution
On a
,
donc
. Comme
est impair,
1 mod 8,
2 mod 4,
donc
est congru à 3 mod 4. D'après la question précédente,
il existe un nombre premier
divisant
et congru à
mod 4. Comme il divise
, il divise aussi
.
- Conclure.
Solution
Soit des entiers
et
tels que
. On a trouvé un nombre premier
divisant
et congru à 3 mod 4. Pour ce nombre premier,
0 mod
.
Donc
est un carré modulo
, ce qui est absurde, car
est congru à 3 mod 4.
Pour aller plus loin
- Systèmes linéaires :
Exercices :
Systèmes linéaires modulaires
I
II
III
- Racines de l'unité dans /
:
Exercices :
I
II
III
- Racine d'un polynôme :
Exercice :
Relèvement
- Authentification :
Exercice :
Authentification
- Exercices sur l'identité de Bezout :
Exercices :
I
II
III
IV
- Critères de divisibilité
Exercices :
I
II
III
-
Algorithme d'exponentiation
Exercices :
Nombre de multiplications
Exercice sur l'exponentiation
- Logarithme discret
Exercices :
Log discret I
Log discret I
-
Factorisation par la méthode de Pollard
- Méthode de cryptologie
Exercices :
RSA I
RSA analyse
RSA création
RSA décryptage
Diffie-Hellman I
Diffie-Hellman I
Factorisation par la méthode de Pollard
Définition : Soit
un entier positif. Un entier
est dit
-friable
si tous ses facteurs premiers sont inférieurs à
.
On appelle
une base de friabilité.
Soit
le ppcm de toutes les puissances de nombres premiers inférieurs ou égaux à
qui sont inférieurs à
.
Pour qu'une puissance
d'un nombre premier soit inférieure à
,
il faut et il suffit que
soit inférieur à
et on a donc
où le produit est pris sur tous les nombres premiers inférieurs à
.
Soit
un entier que l'on désire factoriser.
On va chercher ses facteurs premiers
tels que
soit
-friable.
Pour un tel facteur premier,
divise
et par le
théorème de Fermat,
Théorème :
Soit
un nombre premier impair. Alors pour tout entier
premier à
,
1 mod
.
on a
1 mod
pour tout entier
premier à
et en particulier pour
tout entier
premier à
(d'ailleurs
si on tombe un entier
non premier avec
, on a déjà gagné).
L'algorithme consiste donc à
- choisir un entier
au hasard entre 2 et
-
calculer le pgcd de
et de
-
s'il est égal à 1, pour les diviseurs premiers
de
, calculer successivement
le pgcd de
et de
avec
et remplacer
par
.
Des exemples
Des exemples
Prenons l'entier
et
comme base de friabilité.
On part d'un entier
. Voici le résultat des opérations :
a | q | s | mod N | pgcd() |