Inverse Modulaire

La valeur de l'inverse modulaire de $ a $ par le modulo $ n $ est la valeur $ a^{-1} $ telle que $ a a^{-1} \equiv 1 \pmod n $

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

Si un inverse modulaire existe alors il est unique.

Pour calculer la valeur d'un inverse modulo, utiliser l'algorithme d'euclide étendu qui permet de trouver des solutions à l'identité de Bezout $ au + bv = \text{P.G.C.D.}(a, b) $. Ici, la valeur du pgcd est donnée c'est 1 : $ \text{P.G.C.D.}(a, b) = 1 $, donc seule la valeur de $ u $ est recherchée.

Exemple : $ 3^-1 \equiv 4 \mod 11 $ car $ 4 \times 3 = 12 $ et $ 12 \equiv 1 \mod 11 $

dCode utilise l'algorithme d'Euclide étendu pour calculer l'inverse modulo N et des fonctions à précisions arbitraires pour avoir des résultats avec de très grands nombres. Le résultat s'appuie aussi sur le calcul de modulo.

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

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

Un inverse multiplicatif est l'autre nom d'un inverse modulaire.