Inverse multiplicatif modulo n

L'inverse multiplicatif d'un entier modulo n est le résidu inverse qui satisfait entier fois inverse congruent à un modulo n. Cet inverse existe si et seulement si l'entier et le module sont premiers entre eux — leur plus grand commun diviseur vaut un. Tutoriels de cryptographie, étapes de clé privée RSA, division modulaire en programmation de concours et calculs sur groupes cycliques exigent cette opération, or de nombreux langages n'exposent qu'un GCD binaire et vous laissent les coefficients de Bézout.

Ce qu'est un inverse multiplicatif modulo n et quand il existe

En arithmétique ordinaire tout nombre non nul a un inverse multiplicatif : on divise par lui et on obtient un. En arithmétique modulaire la même idée devient une congruence. On dit que inverse est un inverse multiplicatif d'un entier modulo n lorsque l'entier fois inverse laisse un reste un en division par le module.

Comme les résidus tournent tous les n pas, tout entier n'a pas un tel inverse. L'obstacle est arithmétique, pas flottant : si d égale le gcd de l'entier et du module et d est supérieur à un, alors l'entier fois tout candidat est multiple de d, donc le produit ne peut jamais être congruent à un, qui n'est pas multiple de d.

Inversement, l'identité de Bézout garantit des entiers x et y avec entier fois x plus module fois y égal à un exactement quand ce gcd vaut un, et réduire x modulo n donne l'inverse. Les ingénieurs rencontrent cette condition en divisant dans un anneau fini, en choisissant des exposants de déchiffrement RSA qui inversent l'exposant public modulo phi de N, en annulant des multiplications modulaires dans des pipelines de hachage, ou en résolvant des congruences linéaires en programmation compétitive.

Renvoyer une erreur explicite lorsque la paire n'est pas première entre elle est plus utile qu'un échec silencieux : le client apprend qu'aucun inverse n'existe et peut brancher sur le gcd au lieu de deviner quelle bibliothèque a renvoyé un mauvais résidu. La calculatrice traite donc une paire non première entre elle comme entrée invalide, plutôt que d'inventer un inverse fictif qui casserait tout contrôle ultérieur de la congruence définissante.

Comment cette calculatrice exécute l'algorithme d'Euclide étendu

L'implémentation réduit d'abord l'entier dans la classe de résidu non négative residue de zéro à n moins un, puis applique l'algorithme d'Euclide étendu à la paire residue et modulus. Chaque étape enregistre le quotient entier et met à jour les coefficients de Bézout de sorte qu'à la fin le coefficient de residue multiplie residue plus un coefficient du module égale le gcd. Si le gcd vaut un, le coefficient de residue est réduit dans l'intervalle de zéro à n moins un et renvoyé comme inverse.

Les valeurs absolues sont bornées par un billion afin que tout doublement intermédiaire du produit modulaire reste dans la plage d'entiers sûrs de JavaScript. Les entiers négatifs sont acceptés et réduits avant la boucle euclidienne, ainsi une entrée de moins trois modulo onze est traitée comme residue huit et inversée dans cette classe.

Usage pratique, limites, tarification et livraison

Utilisez l'outil navigateur lorsque vous voulez un inverse rapide en lisant une note crypto, en vérifiant une congruence de devoir ou en déboguant une multiplication modulaire. Les entrées acceptées sont des entiers de valeur absolue au plus un billion et des modules de deux à un billion. Les résultats sont déterministes : la même paire donne toujours le même inverse et le même champ check.

Branchez le point de terminaison sur des bacs à sable d'enseignement RSA, des démos d'anneaux finis, des aides de programmation de concours ou tout pipeline entier qui préfère l'arithmétique exacte aux heuristiques approximatives. Gardez la paire dans les bornes publiées, traitez l'erreur de non-primalité relative comme un résultat de premier plan dans vos tests, et vous obtenez un inverse reproductible pour devoirs, greffons LMS et workers en bordure sans dresser un système d'algèbre informatique à vous.