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.
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(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 :
- 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).
Notes et référencesModifier
- (en) Thomas Koshy, Elementary number theory with applications, , 2e éd., 771 p. (ISBN 978-0-12-372487-8, lire en ligne), p. 346