Multiplikatives Inverses modulo n

Das multiplikative Inverse einer ganzen Zahl modulo n ist der Rest inverse, der ganze Zahl mal inverse kongruent eins modulo n erfüllt. Dieses Inverse existiert genau dann, wenn die ganze Zahl und der Modul teilerfremd sind — ihr größter gemeinsamer Teiler ist eins. Kryptografie-Tutorials, RSA-Privatschlüssel-Schritte, modulare Division im Wettbewerbscode und zyklische Gruppenrechnungen brauchen diese Operation, doch viele Sprachen stellen nur einen binären GCD bereit und überlassen Ihnen die Bézout-Koeffizienten.

Was ein multiplikatives Inverses modulo n ist und wann es existiert

In der gewöhnlichen Arithmetik hat jede von null verschiedene Zahl ein multiplikatives Inverses: Division ergibt eins. In der modularen Arithmetik wird dieselbe Idee zur Kongruenz. Wir sagen, inverse sei ein multiplikatives Inverses einer ganzen Zahl modulo n, wenn die ganze Zahl mal inverse bei Division durch den Modul den Rest eins lässt.

Weil Reste alle n Schritte umschlagen, hat nicht jede ganze Zahl ein solches inverse. Das Hindernis ist zahlentheoretisch, nicht gleitkommaartig: ist d der gcd der ganzen Zahl und des Moduls und d größer als eins, so ist die ganze Zahl mal jeder Kandidat ein Vielfaches von d und das Produkt kann nie kongruent zu eins sein, das kein Vielfaches von d ist.

Umgekehrt garantiert Bézouts Identität ganze Zahlen x und y mit ganze Zahl mal x plus Modul mal y gleich eins genau dann, wenn dieser gcd eins ist; x modulo n liefert das inverse. Ingenieure treffen diese Bedingung beim Teilen in endlichen Ringen, beim Wählen von RSA-Entschlüsselungsexponenten, die den öffentlichen Exponenten modulo phi von N invertieren, beim Rückgängigmachen modularer Multiplikationen in Hash-Pipelines oder beim Lösen linearer Kongruenzen im Wettbewerbsprogrammieren.

Ein expliziter Fehler bei nicht teilerfremden Paaren ist nützlicher als stilles Versagen: der Client erfährt, dass kein inverse existiert, und kann am gcd verzweigen, statt zu raten, welche Bibliothek einen falschen Rest lieferte. Der Rechner behandelt ein nicht teilerfremdes Paar daher als ungültige Eingabe, statt ein Platzhalter-inverse zu erfinden, das jede spätere Prüfung der definierenden Kongruenz zerstören würde.

Wie dieser Rechner den erweiterten euklidischen Algorithmus ausführt

Die Implementierung reduziert die ganze Zahl zuerst in die nichtnegative Restklasse residue von null bis n minus eins und wendet dann den erweiterten euklidischen Algorithmus auf das Paar residue und modulus an. Jeder Schritt speichert den ganzzahligen Quotienten und aktualisiert die Bézout-Koeffizienten so, dass am Ende der Koeffizient von residue mal residue plus ein Koeffizient des Moduls den gcd ergibt. Ist der gcd eins, wird der Koeffizient von residue in den Bereich null bis n minus eins reduziert und als inverse zurückgegeben.

Absolutwerte sind durch eine Billion begrenzt, damit jedes Zwischenverdoppeln des modularen Produkts im sicheren Ganzzahlbereich von JavaScript bleibt. Negative ganze Zahlen werden akzeptiert und vor der euklidischen Schleife reduziert, sodass eine Eingabe von minus drei modulo elf als residue acht behandelt und in dieser Klasse invertiert wird.

Praktischer Einsatz, Grenzen, Preise und Bereitstellung

Nutzen Sie das Browser-Tool, wenn Sie ein schnelles inverse beim Lesen einer Krypto-Notiz, Prüfen einer Hausaufgaben-Kongruenz oder Debuggen eines modularen Multiplikationsschritts brauchen. Akzeptierte Eingaben sind ganze Zahlen mit Absolutwert höchstens einer Billion und Module von zwei bis einer Billion. Ergebnisse sind deterministisch: dasselbe Paar liefert stets dasselbe inverse und dasselbe check-Feld.

Verdrahten Sie den Endpunkt in RSA-Lehrsandboxes, Endring-Demos, Wettbewerbshilfen oder jede ganzzahlige Pipeline, die exakte Arithmetik heuristischen Näherungen vorzieht. Halten Sie das Paar in den veröffentlichten Grenzen, behandeln Sie einen Nicht-teilerfremd-Fehler als erstklassiges Testergebnis, und Sie erhalten ein reproduzierbares inverse für Hausaufgaben, LMS-Plugins und Edge-Worker, ohne ein eigenes Computeralgebrasystem aufzustellen.