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 ℤn. 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 équivalenteModifier

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éModifier

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 PGCD(a, n) = 1, 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.

ExempleModifier

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

 

Cela revient à calculer u vérifiant

 

Dans l'ensemble de ℤ11, 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 ℤ11, 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 calculModifier

Algorithme d'Euclide étenduModifier

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

 

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

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

 

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(an) = 1 est d'ores et déjà connu et non à calculer.

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

Théorème d'EulerModifier

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

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 (ℤ/nℤ)* 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[réf. nécessaire] quand on possède une implémentation de l'exponentiation modulaire. Elle demande cependant :

Notes et référencesModifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Modular multiplicative inverse » (voir la liste des auteurs).
  1. (en) Thomas Koshy, Elementary number theory with applications, , 2e éd., 771 p. (ISBN 978-0-12-372487-8, lire en ligne), p. 346

Articles connexesModifier