Division modulaire

La division modulaire cherche un résidu q tel que b multiplié par q soit congruent à a modulo n. En arithmétique ordinaire vous divisez simplement ; en arithmétique modulaire la division est une multiplication par l'inverse modulaire du diviseur. Cet inverse n'existe que lorsque b et n sont premiers entre eux. Les laboratoires de cryptographie, la programmation de concours, les devoirs sur les corps finis et les exercices de congruences linéaires ont besoin de cette opération, pourtant de nombreux langages n'exposent qu'un GCD ou un inverse modulaire nu et vous laissent le pas de multiplication. Ce calculateur prend les entiers a, b et le module n, inverse b modulo n avec l'algorithme d'Euclide étendu lorsque c'est possible, multiplie par a et renvoie l'unique quotient non négatif entre zéro et n moins un, avec l'inverse, le gcd et un produit de vérification pour que vous puissiez contrôler le résultat sans refaire les étapes.

Ce que signifie la division modulaire et quand elle est définie

Dans les entiers tout nombre non nul a un réciproque dans les rationnels, de sorte que la division est toujours définie hors du zéro. Modulo n le cadre est plus strict : les résidus forment un anneau et seules les unités—éléments possédant un inverse multiplicatif—peuvent servir de diviseurs légaux. On dit que q est un quotient modulaire de a divisé par b modulo n lorsque b multiplié par q laisse le même reste que a quand les deux produits sont réduits modulo n.

De façon équivalente, q est congruent à a multiplié par l'inverse de b modulo n. L'inverse de b existe si et seulement si le gcd de b et n vaut un ; sinon tout multiple de b partage un facteur avec n et ne peut atteindre toutes les classes de résidus, de sorte qu'aucun q unique ne convient pour un a arbitraire.

Ingénieurs et étudiants rencontrent cette barrière lorsqu'ils divisent dans un module composite qui n'est pas un corps premier, lorsqu'ils annulent un coefficient dans une congruence linéaire ou lorsqu'ils défont une multiplication modulaire dans une étape de hachage ou de chiffrement. Notez que a lui-même n'a pas besoin d'être premier avec n ; seul le diviseur b doit être une unité. Cette asymétrie s'oublie facilement si l'on ne retient que le cas particulier de l'inverse modulaire avec a égal à un.

Usage pratique, limites, tarifs et livraison

Utilisez l'outil du navigateur lorsque vous voulez un quotient modulaire rapide en lisant une note de théorie des nombres, en vérifiant un devoir de la forme b x congruent à a mod n, ou en déboguant un pipeline modulaire qui multiplie déjà par des inverses à la main. Les entrées acceptées sont des entiers a et b de valeur absolue au plus un billion et des modules n de deux à un billion. Les résultats sont déterministes : le même triplet produit toujours les mêmes champs quotient, inverse et check.

Branchez le point de terminaison sur des aides de concours, des démos de corps finis, des bacs à sable d'enseignement RSA qui demandent plus que de simples inverses, ou tout pipeline entier qui préfère l'arithmétique exacte aux heuristiques en virgule flottante. Si vous n'avez besoin que de l'inverse de b sans multiplier par a, préférez la capacité dédiée d'inverse modulaire ; cette page cible l'intention complète de division que l'on cherche comme division modulaire ou a divisé par b mod n.