Inverse Modulaire

La valeur de l'inverse modulaire d'un entier $ a $ modulo $ n $ est la valeur $ a^{-1} $ telle que $ a \cdot a^{-1} \equiv 1 \mod n $

Autrement dit, l'inverse modulaire est un nombre qui, multiplié par $ a $, donne un reste égal à $ 1 $ dans l'arithmétique modulo $ n $.

Il est courant de noter cet inverse modulaire $ u $ et d'utiliser ces équations $$ u \equiv a^{-1} \mod n \\ a u \equiv 1 \mod n $$

L'inverse modulaire de $ a $ modulo $ n $ existe si et seulement si $ \operatorname{pgcd}(a,n) = 1 $, c'est-à-dire si $ a $ et $ n $ sont premiers entre eux.

Si $ \operatorname{pgcd}(a,n) = d > 1 $, alors toute combinaison linéaire $ a u + n v $ est multiple de $ d $ et ne peut donc jamais être égale à $ 1 $.

Si un inverse modulaire existe, alors il est unique modulo $ n $. Toutes les solutions sont de la forme : $ u + k n $ avec $ k $ un entier relatif.

Pour calculer un inverse modulaire de $ a $ modulo $ n $, utiliser l'algorithme d'Euclide étendu.

L'algorithme d'Euclide étendu permet de trouver des entiers $ u $ et $ v $ tels que $ a u + n v = \operatorname{pgcd}(a,n) $. Comme $ \operatorname{pgcd}(a,n) = 1 $, alors $ a u + n v = 1 $, en réduisant cette égalité modulo $ n $, le terme $ n v $ disparaît et il reste : $ a u \equiv 1 \mod n $. La valeur $ u $ est donc un inverse modulaire de $ a $ modulo $ n $.

Utiliser l'identité de Bezout, aussi disponible sur dCode.

Le mot clé invmod est l'abréviation de inverse modulaire.

En programmation ou en calcul formel, invmod(a,n) désigne généralement la fonction qui retourne l'inverse modulaire si cet inverse existe.

Un inverse multiplicatif d'un élément est un nombre qui, multiplié par cet élément, donne $ 1 $.

Dans l'arithmétique modulo $ n $, l'inverse multiplicatif de $ a $ est égal à son inverse modulaire.

Dans le chiffrement RSA, la clé privée $ d $ est calculée comme l'inverse modulaire de l'exposant public $ e $ modulo $ \varphi(n) $. Sans inverse modulaire, il serait impossible de construire la clé de déchiffrement.

L'inverse de $ 2 $ modulo un nombre impair $ n $ est toujours égal à $ \frac{n+1}{2} $

En effet : $ 2 \times \frac{n+1}{2} = n + 1 \equiv 1 \mod n $