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 équivalente
modifierD'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é
modifierVu 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.
Exemple
modifierSupposons 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 calcul
modifierAlgorithme d'Euclide étendu
modifierL'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'Euler
modifierCette 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[2] 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
modifier- (en) Thomas Koshy, Elementary number theory with applications, , 2e éd., 771 p. (ISBN 978-0-12-372487-8, lire en ligne), p. 346
- (en) Daniel J. Bernstein, « Curve25519: New Diffie-Hellman Speed Records », Public Key Cryptography - PKC 2006, Springer, lecture Notes in Computer Science, , p. 207–228 (ISBN 978-3-540-33852-9, DOI 10.1007/11745853_14, lire en ligne, consulté le )