Inverse modulaire

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

au\equiv 1{\pmod {n}}.

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, $u$ peut être noté $a^{-1}$ , étant entendu implicitement que l'inversion est modulaire et se fait modulo $n$ .

La définition est donc équivalente à :

u\equiv a^{-1}{\pmod {n}}.

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

Définition équivalente

D'après la définition ci-dessus, $u$ est un inverse de $a$ modulo $n$ s'il existe un entier $v$ tel que

1-au=nv

ou encore : tel que

au+nv=1.

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

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

u\equiv 3^{-1}{\pmod {11}}.

Cela revient à calculer u vérifiant

3u\equiv 1{\pmod {11}}.

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

3\times 4=12\equiv 1{\pmod {11}},

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

u=4+11k,\quad k\in \mathbb {Z} ,

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.

au+bv={\text{PGCD}}(a,b)\,

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

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

au+nv=1,

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[1].

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

a^{\varphi (n)}\equiv 1{\pmod {n}}

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

a^{-1}\equiv a^{\varphi (n)-1}{\pmod {n}}.

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

a^{-1}\equiv a^{n-2}{\pmod {n}}.

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 utile 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

(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).

(en) Thomas Koshy, Elementary number theory with applications, 2007, 2^e é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,‎ 2006, p. 207–228 (ISBN 978-3-540-33852-9, DOI 10.1007/11745853_14, lire en ligne, consulté le 30 août 2021)

Articles connexes

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] (en) Thomas Koshy, Elementary number theory with applications, 2007, 2^e éd., 771 p. (ISBN 978-0-12-372487-8, lire en ligne), p. 346

[2] (en) Daniel J. Bernstein, « Curve25519: New Diffie-Hellman Speed Records », Public Key Cryptography - PKC 2006, Springer, lecture Notes in Computer Science,‎ 2006, p. 207–228 (ISBN 978-3-540-33852-9, DOI 10.1007/11745853_14, lire en ligne, consulté le 30 août 2021)