Inverse Modulo Rechner

Berechnung des multiplikativen Inversen x mit a·x ≡ 1 (mod m)

Modulares Inverses berechnen

Multiplikatives Inverses modulo m

Gesucht ist x mit a·x ≡ 1 (mod m). Die Lösung existiert genau dann, wenn gcd(a, m) = 1. Berechnung über erweiterten Euklidischen Algorithmus.

7 · x ≡ 1 (mod 5)
Parameter eingeben
Ganze Zahl a ≥ 1
Ganze Zahl m ≥ 2
Berechnungsergebnis
x =
Berechnung: Finde x mit a·x ≡ 1 (mod m)

Modulare Inverse Info

Existenzbedingung

Das Inverse existiert nur falls: gcd(a,m) = 1

gcd(a,m)=1 teilerfremd x⁻¹

Definition: x ist das modulare Inverse von a modulo m, wenn a·x ≡ 1 (mod m)
Berechnung: Erweiterter Euklidischer Algorithmus

Kleine Beispiele
3⁻¹ mod 7: 3·5 ≡ 1 (mod 7) → x = 5
2⁻¹ mod 5: 2·3 ≡ 1 (mod 5) → x = 3
6⁻¹ mod 9: gcd(6,9)=3 → kein Inverses

Formeln und Definitionen

Definition
\[a \cdot x \equiv 1 \pmod{m}\]

x ist das modulare Inverse von a modulo m

Existenzbedingung
\[\gcd(a, m) = 1\]

a und m müssen teilerfremd sein

Erweiterter Euklid
\[as + mt = \gcd(a, m) = 1\] \[\Rightarrow s \equiv a^{-1} \pmod{m}\]

Berechnung über erweiterten Euklidischen Algorithmus

Fermat (m prim)
\[a^{m-1} \equiv 1 \pmod{m}\] \[\Rightarrow a^{-1} \equiv a^{m-2} \pmod{m}\]

Für Primzahlen m mittels Fermats kleinem Satz

Beispiel: Inverses von 3 modulo 7

Schritt-für-Schritt mit erweitertem Euklid
Schritt 1: Euklidischer Algorithmus
7 = 2 · 3 + 1
3 = 3 · 1 + 0

gcd(3,7) = 1 ✓ (Inverses existiert)

Schritt 2: Rückwärts einsetzen
1 = 7 - 2 · 3
1 = 7 · 1 + 3 · (-2)

Daraus folgt: s = -2, t = 1

3⁻¹ ≡ -2 ≡ 5 (mod 7)
Verifikation
\[3 \cdot 5 = 15\] \[15 = 2 \cdot 7 + 1\] \[15 \equiv 1 \pmod{7} \checkmark\]
Alle Kandidaten prüfen
3·1 = 3 ≢ 1 (mod 7)
3·2 = 6 ≢ 1 (mod 7)
3·3 = 9 ≡ 2 (mod 7)
3·4 = 12 ≡ 5 (mod 7)
3·5 = 15 ≡ 1 (mod 7) ✓
3·6 = 18 ≡ 4 (mod 7)
Algorithmus-Schritte
1. gcd berechnen
2. Rückwärts einsetzen
3. Koeffizienten s finden
4. Positiv machen

Systematische Berechnung über erweiterten Euklidischen Algorithmus

Anwendungen modularer Inversen

Modulare Inversen sind zentral in Zahlentheorie und Kryptographie:

Kryptographie
  • RSA-Verschlüsselung (d ≡ e⁻¹ mod φ(n))
  • Elliptische Kurven-Kryptographie
  • Digitale Signaturen
  • Diffie-Hellman-Schlüsselaustausch
Zahlentheorie
  • Chinesischer Restsatz
  • Lösen linearer Kongruenzen
  • Modulare Bruchrechnung
  • Primzahltests
Informatik
  • Hash-Funktionen
  • Fehlerkorrekturcodes
  • Pseudozufallsgeneratoren
  • Modulare Exponentiation
Mathematik
  • Gruppentheorie (Einheiten-Gruppe)
  • Algebraische Strukturen
  • Diophantische Gleichungen
  • Abstrakte Algebra

Modulare Inversen: Grundlage moderner Kryptographie

Modulare Inversen bilden ein fundamentales Konzept der elementaren Zahlentheorie mit enormer praktischer Bedeutung. Das multiplikative Inverse von a modulo m ist die Zahl x, für die a·x ≡ 1 (mod m) gilt. Diese scheinbar einfache Definition führt zu tiefgreifenden mathematischen Strukturen und ermöglicht moderne kryptographische Verfahren wie RSA. Der erweiterte Euklidische Algorithmus bietet einen effizienten Weg zur Berechnung.

Eigenschaften
  • Existenz nur bei gcd(a,m) = 1
  • Eindeutigkeit modulo m
  • Gruppenstruktur der Einheiten
  • Erweiterung des Bruchkonzepts
Bedeutung
  • Grundlage der RSA-Kryptographie
  • Lösung linearer Kongruenzen
  • Modulare Arithmetik
  • Algebraische Zahlentheorie
Berechnung
  • Erweiterter Euklidischer Algorithmus
  • Fermats kleiner Satz (bei Primzahlen)
  • Eulers Theorem (allgemein)
  • Schnelle modulare Exponentiation
Zusammenfassung

Modulare Inversen verbinden elementare Zahlentheorie mit hochmoderner Kryptographie. Die Existenzbedingung gcd(a,m) = 1 definiert die Struktur der Einheitengruppe modulo m und ermöglicht sichere Verschlüsselungsverfahren. Der erweiterte Euklidische Algorithmus bietet nicht nur einen konstruktiven Existenzbeweis, sondern auch einen effizienten Berechnungsweg. Von der antiken Zahlentheorie bis zur digitalen Sicherheit zeigen modulare Inversen die zeitlose Relevanz mathematischer Grundlagen.

Ist diese Seite hilfreich?            
Vielen Dank für Ihr Feedback!

Das tut uns leid

Wie können wir die Seite verbessern?