Inverse modulaire

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier relatif  pour la multiplication modulo  est un entier  satisfaisant l'équation :

En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤ. Une fois ainsi défini,  peut être noté , étant entendu implicitement que l'inversion est modulaire et se fait modulo .

La définition est donc équivalente à :

L'inverse de a modulo  existe si et seulement si  et  sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par  modulo  équivaut à la multiplication par son inverse.

Définition équivalente
D'après la définition ci-dessus,  est un inverse de  modulo  s'il existe un entier  tel que

ou encore : tel que

Existence et unicité
Vu ce qui précède, a possède un inverse modulo n si et seulement s'il existe deux entiers u et v tels que au + nv = 1. D'après le théorème de Bachet-Bézout, ceci a lieu si et seulement si  c'est-à-dire si a et n sont premiers entre eux.

De plus, si un tel inverse existe alors il est unique (modulo n) et peut se calculer grâce à l'algorithme d'Euclide étendu ou au théorème d'Euler : cf. section « Méthodes de calcul » ci-dessous.

Exemple

Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11.

Cela revient à calculer u vérifiant

Dans l'ensemble de ℤ, une solution est 4 car

et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4.

À partir du moment où l'on a trouvé l'inverse de 3 dans ℤ, on peut trouver une infinité d'autres entiers u qui satisfont aussi cette congruence. Il suffit d'ajouter des multiples de n = 11 à l'inverse que nous avons trouvé. Autrement dit, les solutions sont

c'est-à-dire les éléments de {…, –18, –7, 4, 15, 26, …}.

Méthodes de calcul

Algorithme d'Euclide étendu
L'algorithme d'Euclide étendu permet génériquement de trouver des solutions à l'identité de Bézout.

où a, b sont connus et u, v et PGCD(a, b) sont des nombres recherchés.

Comme vu plus haut, l'inverse modulaire  est solution de 

où a et n sont connus et v un entier qui sera éliminé. On se conforme ici à la forme que l'algorithme d'Euclide étendu résout, à la différence près que PGCD(a, n) = 1 est d'ores et déjà connu et non à calculer.

La complexité de l'algorithme est en O(log(n)) quand |a| < n.

Théorème d'Euler
Cette méthode est une alternative à l'algorithme d'Euclide : on peut utiliser le théorème d'Euler pour calculer l'inverse modulaire.

Selon ce théorème, si a est premier avec n, c'est-à-dire si PGCD(a, n) = 1, alors

où φ(n) est l'indicatrice d'Euler. Cela résulte du fait que a appartient au groupe des unités  si et seulement si a est premier avec n. L'inverse modulaire est donc donné directement par

Dans le cas particulier où n est premier, l'équation ci-dessus devient :

Cette méthode de calcul, généralement plus lente que l'algorithme d'Euclide, est parfois utilisée quand on possède une implémentation de l'exponentiation modulaire. Elle demande cependant :
 la connaissance de φ(n), dont le calcul le plus rapide reste par factorisation de n (c'est sur la difficulté calculatoire à factoriser de grands entiers que repose la sûreté du chiffrement RSA) ;
 un calcul suffisamment rapide de l'exponentiation modulaire, qui peut se faire par exponentiation rapide en O(log φ(n)) = O(log n) (la méthode de réduction de Montgomery, plus efficace pour de grandes valeurs de n, demande le calcul d'un inverse modulo n, ce qui est l'objectif).
L'avantage de cette méthode est que l'opération d'inverse se fait en temps constant ce qui permet de garantir certaines propriétés utiles pour se prémunir contre les attaques par canaux auxiliaires notamment dans le cadre d'implémentation de Cryptographie asymétrique.

Notes et références

Articles connexes
 Cryptographie asymétrique
 Théorie des nombres

Arithmétique modulaire