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'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 ${\text{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, à la différence près que ${\text{PGCD}}(a,n)=1$ est d'ores et déjà connu et non à calculer.

La complexité de l'algorithme est en ${\mathcal {O}}(\log ^{2}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 ${\text{PGCD}}(a,n)=1$ , alors

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

où $\varphi (n)$ est l'indicatrice d'Euler. Cela résulte du fait que $a$ appartient au groupe des unités $\mathbb {Z} /n\mathbb {Z} ^{\times }$ si et seulement si $a$ est premier avec $n$ . L'inverse modulaire est alors 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 $\varphi (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 ${\mathcal {O}}(\log \varphi (n))\approx {\mathcal {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.

Inverse modulaire

Existence et unicité

Exemple

Méthodes de calcul

Algorithme d'Euclide étendu

Théorème d'Euler

Notes et références

Articles connexes

Related Articles