Inverse modulaire

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

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

où ${\displaystyle a}$, ${\displaystyle b}$ sont connus et ${\displaystyle u}$, ${\displaystyle v}$ et ${\displaystyle {\text{PGCD}}(a,b)}$ sont des nombres recherchés.

Comme vu plus haut, l'inverse modulaire ${\displaystyle u}$ est solution de

${\displaystyle au+nv=1,}$

où ${\displaystyle a}$ et ${\displaystyle n}$ sont connus et ${\displaystyle v}$ un entier qui sera éliminé. On se conforme ici à la forme que l'algorithme d'Euclide étendu, à la différence près que ${\displaystyle {\text{PGCD}}(a,n)=1}$ est d'ores et déjà connu et non à calculer.

La complexité de l'algorithme est en ${\displaystyle {\mathcal {O}}(\log ^{2}n)}$quand ${\displaystyle |a|<n}$.

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 ${\displaystyle a}$ est premier avec ${\displaystyle n}$, c'est-à-dire si ${\displaystyle {\text{PGCD}}(a,n)=1}$, alors

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

où ${\displaystyle \varphi (n)}$ est l'indicatrice d'Euler. Cela résulte du fait que ${\displaystyle a}$ appartient au groupe des unités ${\displaystyle \mathbb {Z} /n\mathbb {Z} ^{\times }}$ si et seulement si ${\displaystyle a}$ est premier avec ${\displaystyle n}$. L'inverse modulaire est alors donné directement par

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

Dans le cas particulier où ${\displaystyle n}$ est premier, l'équation ci-dessus devient :

${\displaystyle 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 ${\displaystyle \varphi (n)}$, dont le calcul le plus rapide reste par factorisation de ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle n}$, demande le calcul d'un inverse modulo ${\displaystyle 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.

• Cryptographie asymétrique
• Théorie des nombres

• Arithmétique et théorie des nombres