Was ist eine modulare Inverse?
Beim Rechnen modulo m, also mit Resten bei der Division durch m, gibt es keine gewöhnliche Division. An ihre Stelle tritt die Multiplikation mit der modularen Inversen. Die modulare Inverse von a ist die Zahl x zwischen 0 und m − 1, für die a · x bei Division durch m den Rest 1 lässt. Man schreibt a · x ≡ 1 (mod m) oder kurz x = a⁻¹ mod m.
Eine solche Zahl gibt es nicht immer. Sie existiert genau dann, wenn a und m teilerfremd sind, ihr größter gemeinsamer Teiler also 1 ist. Modulo 9 hat 6 zum Beispiel keine Inverse, denn 6 und 9 haben den gemeinsamen Teiler 3, und 6 · x ergibt modulo 9 immer 0, 3 oder 6. Ist m eine Primzahl, besitzt dagegen jede Zahl, die kein Vielfaches von m ist, eine Inverse.
Der Rechner bestimmt zuerst den ggT mit dem euklidischen Algorithmus und zeigt jede Division mit Rest als Rechenschritt. Ist der ggT 1, liefert die Rückwärtsrechnung die Bézout-Darstellung s · a + k · m = 1. Der Faktor s, auf den Bereich 0 bis m − 1 gebracht, ist die gesuchte Inverse.
Anwendungen und Rechentipps
Die bekannteste Anwendung ist das RSA-Verfahren der Kryptografie. Dort wird der private Schlüssel d als modulare Inverse des öffentlichen Exponenten e modulo φ(n) berechnet. Das Beispiel oben mit e = 17 und φ(n) = 3120 stammt aus einem klassischen Lehrbuchbeispiel mit den Primzahlen 61 und 53. In echten Anwendungen sind die Zahlen mehrere hundert Stellen lang; der Rechner ist auf 15 Stellen begrenzt und dient dem Verständnis.
Weitere Anwendungen sind das Lösen linearer Kongruenzen wie 17x ≡ 5 (mod 3120), der chinesische Restsatz, affine Chiffren, Prüfziffernverfahren und das Rechnen in endlichen Körpern. Bei einer Kongruenz a · x ≡ b multiplizieren Sie beide Seiten mit der Inversen von a und erhalten x ≡ b · a⁻¹. So wird aus einer scheinbar schwierigen Gleichung eine einfache Multiplikation.
Negative Zahlen und Zahlen größer als m reduziert der Rechner zuerst auf den Bereich von 0 bis m − 1. So ist −3 modulo 7 gleich 4, und die Inverse von −3 ist dieselbe wie die von 4, nämlich 2, denn 4 · 2 = 8 lässt bei Division durch 7 den Rest 1.
Bei kleinem Modul können Sie die Inverse auch durch Probieren finden oder bei einem Primzahlmodul p mit dem kleinen Satz von Fermat als a hoch (p − 2) berechnen. Für große Zahlen ist der erweiterte euklidische Algorithmus deutlich schneller, weil er nur logarithmisch viele Schritte braucht. Reste allgemein berechnet der Modulo-Rechner, den größten gemeinsamen Teiler der ggT-und-kgV-Rechner.
Tipps und typische Fehler
Modular rechnen.
- ggT: Muss 1 sein.
- Probe: a·x mod m = 1.
- Negativ: Plus m rechnen.
- Primzahlmodul: Immer lösbar.
Weitere Rechner: Mathe & Formeln
Häufige Fragen
Wann existiert eine modulare Inverse?
Genau dann, wenn a und m teilerfremd sind, also ggT(a, m) = 1 gilt.
Wie berechne ich die modulare Inverse?
Mit dem erweiterten euklidischen Algorithmus: Aus s · a + k · m = 1 folgt a⁻¹ ≡ s (mod m).
Was ist die Inverse von 3 modulo 11?
4, denn 3 · 4 = 12 lässt bei Division durch 11 den Rest 1.
Wie löse ich eine lineare Kongruenz?
Beide Seiten mit der Inversen von a multiplizieren: aus a·x ≡ b folgt x ≡ b·a⁻¹ (mod m).
Was ist die Bézout-Darstellung?
Die Darstellung des ggT als s·a + k·m mit ganzen Zahlen s und k.
- modulare Inverse berechnen
- multiplikatives Inverses modulo
- erweiterter euklidischer Algorithmus
- Inverse mod m
- RSA privater Schlüssel berechnen
- Kongruenz lösen
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.