Startseite › Rechner › Rechner für modulares Inverses

Rechner für modulares Inverses

Gib eine Zahl a und einen Modulus m ein, um x mit a × x ≡ 1 (mod m) zu finden. Der Rechner prüft, ob das Inverse existiert (ggT(a, m) = 1), zeigt jeden Schritt des erweiterten euklidischen Algorithmus und funktioniert mit ganzen Zahlen von Hunderten Stellen.

Zuletzt aktualisiert:

Ganze Zahl, darf negativ oder riesig sein. Ausdrücke wie 2^64+1 funktionieren.

Ganze Zahl ≥ 2

Gib deine Werte ein, um das Ergebnis zu sehen.
Anzeige
Anzeige

Anleitung: Rechner für modulares Inverses

  1. Gib a ein, die Zahl, die du invertieren möchtest.
  2. Gib den Modulus m ein (2 oder mehr). Potenzen wie 2^61-1 werden akzeptiert.
  3. Klicke auf Inverses berechnen, um a⁻¹ mod m zu erhalten.
  4. Lies die Schritte: die euklidischen Divisionen und das Rückwärtseinsetzen.
  5. Kopiere das Ergebnis oder lade die Algorithmustabelle als CSV herunter.

Erweiterter euklidischer Algorithmus: Rechenbeispiel

Finde 17⁻¹ mod 3120. Teile wiederholt und notiere, wie sich jeder Rest aus 3120 und 17 zusammensetzt:

DivisionRestAls s·3120 + t·17
3120 = 183 × 17 + 991·3120 − 183·17
17 = 1 × 9 + 88−1·3120 + 184·17
9 = 1 × 8 + 112·3120 − 367·17

Der ggT ist 1, also existiert das Inverse, und 2·3120 − 367·17 = 1. Reduktion mod 3120 ergibt t = −367 ≡ 3120 − 367 = 2753. Probe: 17 × 2753 = 46,801 = 15 × 3120 + 1 ✓.

Kleine Inversentabelle (mod 11)

Da 11 eine Primzahl ist, hat jede Zahl von 1 bis 10 ein Inverses modulo 11. Beachte, dass 1 und 10 (≡ −1) jeweils ihr eigenes Inverses sind.

a12345678910
a⁻¹ mod 1116439287510

Tipps

  • Um eine lineare Kongruenz a·x ≡ b (mod m) mit ggT(a, m) = 1 zu lösen, multipliziere beide Seiten mit dem Inversen: x ≡ b · a⁻¹ (mod m).
  • Das Inverse ist modulo m eindeutig: Es gibt genau eine Lösung zwischen 0 und m − 1.
  • Beim Modulus 26 (das Alphabet) haben nur die 12 zu 26 teilerfremden Zahlen (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25) ein Inverses – deshalb schränken affine Chiffren ihren Schlüssel ein.

Häufige Fragen

Was ist ein modulares Inverses?

Das modulare (multiplikative) Inverse von a modulo m ist die Zahl x zwischen 0 und m − 1 mit a × x ≡ 1 (mod m). Zum Beispiel ist 3⁻¹ mod 11 = 4, weil 3 × 4 = 12 = 11 + 1. Es übernimmt in der modularen Arithmetik die Rolle der Division.

Wann existiert ein modulares Inverses?

Genau dann, wenn a und m teilerfremd sind, also ggT(a, m) = 1. Haben sie einen gemeinsamen Faktor g > 1, lässt jedes Vielfache von a einen Rest, der ein Vielfaches von g ist, und kann daher nie 1 sein. Zum Beispiel hat 6 kein Inverses mod 9, weil ggT(6, 9) = 3. Ist m eine Primzahl, hat jedes a, das nicht durch m teilbar ist, ein Inverses.

Wie findet der erweiterte euklidische Algorithmus das Inverse?

Er führt den normalen euklidischen Algorithmus für ggT(a, m) aus und verfolgt dabei die Koeffizienten s und t, sodass jeder Rest gleich s·m + t·a ist. Erreicht der Rest ggT = 1, gilt s·m + t·a = 1, und nach Reduktion mod m bleibt t·a ≡ 1 – also ist t mod m das Inverse.

Wie wird das modulare Inverse bei RSA verwendet?

Der private Exponent d ist das Inverse des öffentlichen Exponenten e modulo φ(n) (oder λ(n)). Im klassischen Lehrbuchbeispiel ergeben e = 17 und φ(n) = 3120 den Wert d = 17⁻¹ mod 3120 = 2753, denn 17 × 2753 = 46,801 = 15 × 3120 + 1.

Kann ich stattdessen den kleinen fermatschen Satz verwenden?

Ja, wenn m eine Primzahl ist: a⁻¹ ≡ a^(m − 2) (mod m). Für 3 mod 11 ist das 3⁹ mod 11 = 4. Der erweiterte euklidische Algorithmus ist schneller und funktioniert auch, wenn m keine Primzahl ist – deshalb nutzt dieser Rechner ihn.

Was ist mit negativen Zahlen?

Ein negatives a wird zuerst in den Bereich 0 bis m − 1 reduziert (−7 mod 26 = 19) und dann invertiert. Die Antwort wird als kleinstes positives Inverses angegeben; jeder Wert, der sich um ein Vielfaches von m unterscheidet, wie der angezeigte negative Repräsentant, ist ebenfalls ein Inverses.

Werden alle Tools auf FreeToolCabin auf Qualität und Genauigkeit getestet?

Ja. Jedes Tool auf der Website durchläuft automatische Tests in echten Browsern, die prüfen, ob das Ergebnis stimmt und keine Fehler auftreten. Wenn du einen Fehler findest oder einen Vorschlag hast, schreib uns an [email protected] – wir sehen es uns an.

Ähnliche Tools

Alle Algebra- & Analysisrechner ansehen →