Calculateur d'inverse modulaire

Un inverse multiplicatif d'un entier a modulo m est un entier x dont le produit avec a donne un reste de 1 après division par m. En termes de congruences, a fois x est congru à 1 modulo m. Ce calculateur trouve le plus petit inverse non négatif grâce à l'algorithme d'Euclide étendu, puis affiche une vérification par multiplication. Le module doit être un entier supérieur à un. L'inverse existe exactement lorsque a et m sont premiers entre eux, c'est-à-dire lorsque leur plus grand commun diviseur vaut 1. S'ils partagent un facteur plus grand, tout produit contenant a reste divisible par ce facteur modulo m et ne peut jamais donner un reste de 1. Par exemple, 6 n'a pas d'inverse modulo 15, car leur plus grand commun diviseur est 3. En revanche, 3 a pour inverse 4 modulo 11 : 3 fois 4 vaut 12, dont la division par 11 laisse un reste de 1. L'algorithme d'Euclide étendu ne calcule pas seulement le plus grand commun diviseur. Il trouve aussi des coefficients x et y tels que ax plus my soit égal à ce diviseur. Lorsque celui-ci vaut 1, réduire x modulo m fournit l'inverse modulaire. Si x est négatif, ajouter suffisamment de multiples de m le ramène dans l'intervalle standard de zéro à m moins un sans changer sa classe de congruence. Les inverses modulaires remplacent la division en arithmétique modulaire. La division ordinaire ne s'applique pas directement aux classes de résidus, car différents entiers représentent le même résidu. Diviser par a modulo m revient à multiplier par son inverse, à condition qu'il existe. Cette technique est essentielle pour résoudre des congruences linéaires, simplifier des fractions modulaires, appliquer le théorème chinois des restes et construire de nombreux algorithmes de théorie des nombres. La cryptographie utilise largement les inverses modulaires. La génération de clés RSA calcule l'inverse d'un exposant modulo une valeur liée à l'indicatrice d'Euler, tandis que les courbes elliptiques utilisent des inverses dans les formules de points sur des corps finis. La théorie des codes, les sommes de contrôle, les générateurs pseudo-aléatoires et le calcul formel reposent aussi sur des calculs d'inverses efficaces. Les implémentations cryptographiques réelles emploient des routines soigneusement conçues pour grands entiers et à temps constant plutôt que l'arithmétique du navigateur, mais la théorie est la même. L'inverse est unique modulo m, et non comme entier ordinaire. Si 4 est un inverse de 3 modulo 11, alors 15, moins 7 et tous les nombres différant de 4 d'un multiple de 11 représentent le même résidu inverse. Le calculateur affiche 4, car le plus petit représentant non négatif est plus facile à comparer et à réutiliser. Pour vérifier un résultat, multipliez l'entier initial par l'inverse affiché, divisez par le module et vérifiez que le reste vaut 1. La même règle s'applique aux entrées négatives, car les résidus peuvent toujours être normalisés dans l'intervalle standard. Si aucun inverse n'existe, calculez séparément le plus grand commun diviseur : toute valeur supérieure à 1 prouve l'obstacle.