Modulare Inverse berechnen
Eine modulare Inverse macht eine Multiplikation innerhalb eines Moduls rückgängig. Die Seite erzeugt keine RSA-Schlüssel und faktorisiert nicht.
So geht es
- Eine beliebige ganze Zahl a eingeben, auch negativ.
- Einen positiven Modul m größer als 1 eingeben.
- Berechnen, um gegebenenfalls das eindeutige x von 0 bis m−1 zu erhalten.
- Bézout-Zeile und tatsächlichen Produktrest prüfen.
Bedingung und Formel
Eine Inverse existiert genau bei ggT(a,m)=1. Der erweiterte euklidische Algorithmus findet u,v mit a·u+m·v=1; u modulo m ist die Inverse.
Negatives a wird mit ((a mod m)+m) mod m normalisiert.
Beispiele
3 modulo 11
ggT(3,11)=1 und 3×4=12; 12 mod 11=1, also ist 4 die Inverse.
−3 modulo 11
−3 wird zu 8; 8×7=56 und 56 mod 11=1, also ist 7 die Inverse.
6 modulo 9
ggT(6,9)=3; deshalb gibt es keine Inverse.
Grenzen und Umfang
- Je Eingabe höchstens 200 Dezimalziffern; führende Nullen zählen.
- Dezimalzahlen, Exponentialschreibweise, Einheiten, innere Leerzeichen und Infinity werden abgelehnt.
- Modul 0, 1 oder negativ ist ungültig. a=0 ist erlaubt, besitzt für m>1 aber keine Inverse.
- Das Ergebnis ist exakt; dies ist kein Schlüsselgenerator oder Sicherheitsdienst.
Häufige Fragen
Warum muss der ggT 1 sein?
Ein gemeinsamer Faktor größer als 1 teilt jedes Produkt a×x; dessen Rest kann nicht 1 sein.
Kann eine negative Zahl eine Inverse haben?
Ja; sie wird zuerst auf ihren nichtnegativen Rest reduziert.
Warum nur eine Antwort?
Alle Inversen unterscheiden sich um Vielfache von m; gezeigt wird die eindeutige von 0 bis m−1.
Ist das dasselbe wie 1/a?
Nein; gesucht ist eine ganze Zahl, deren Produkt modulo m den Rest 1 hat.