Fotools
EN

Kongruenzgleichungslöser

Eingabeparameter

Schnellbeispiel:

Berechnungsergebnis

Parameter eingeben und auf "Gleichung lösen" klicken

Algorithmus-Erklärung:

1. Lineare Kongruenzgleichung ax ≡ b (mod m):
  • Existenz von Lösungen:Die Gleichung hat genau dann eine Lösung, wenn ggT(a, m) b teilt (d. h. b ist durch ggT(a, m) teilbar)
  • Anzahl der Lösungen:Wenn Lösungen existieren, gibt es d = ggT(a, m) verschiedene Lösungen modulo m
  • Lösungsmethode:
    1. Berechne d = ggT(a, m)
    2. Prüfe, ob d b teilt; wenn nicht, gibt es keine Lösung
    3. Teile beide Seiten der Gleichung durch d: (a/d)x ≡ (b/d) (mod m/d)
    4. Verwende den erweiterten euklidischen Algorithmus, um das Inverse von a/d modulo m/d zu finden
    5. Berechne x₀ = a' × (b/d) mod (m/d)
    6. Allgemeine Lösung: x = x₀ + k(m/d), wobei k = 0, 1, ..., d-1
2. Exponentiale Kongruenzgleichung a^x ≡ b (mod m) (Diskreter Logarithmus):
  • Problembeschreibung:Gegeben a, b, m, finde die kleinste nicht-negative ganze Zahl x, so dass a^x ≡ b (mod m)
  • Existenz von Lösungen:
    • Wenn ggT(a, m) = 1 und b ein Element der von a erzeugten zyklischen Gruppe modulo m ist, existiert eine Lösung
    • Überprüfungsmethode: Potenzen von a aufzählen, bis b gefunden wird oder ein vollständiger Zyklus abgeschlossen ist
  • Lösungsmethode:
    • Brute-Force-Suche in einem kleinen Bereich:x = 0, 1, 2, ... aufzählen, bis eine Lösung gefunden wird oder die Suchgrenze erreicht ist
    • Baby-Step-Giant-Step-Algorithmus:Zeitkomplexität O(√m), geeignet für mittelgroße Probleme
    • Pollard-Rho-Algorithmus:Anwendbar für große Primzahlmodule
  • Periodizität:Wenn x₀ eine Lösung ist, dann ist x = x₀ + kφ(m) ebenfalls eine Lösung (wobei φ(m) die eulersche Phi-Funktion ist)
3. Anwendungsszenarien:
  • Kryptografie:RSA, Diffie-Hellman-Schlüsselaustausch, ElGamal-Verschlüsselung
  • Zahlentheorie-Forschung:Primitivwurzeln, quadratische Reste, chinesischer Restsatz
  • Zufallszahlengenerierung:Linearer Kongruenzgenerator (LCG)
  • Hash-Funktionen:Anwendung der modularen Arithmetik in Hash-Tabellen
  • Wettbewerbsprogrammierung:Schnelle Exponentiation, modulares Inverses, zahlentheoretische Probleme

Algorithmus-Komplexität:

  • Lineare Kongruenzgleichungen:O(log m) (Komplexität des erweiterten euklidischen Algorithmus)
  • Exponentiale Kongruenzgleichungen (Brute Force):O(n), wobei n die Suchgrenze ist
  • Exponentiale Kongruenzgleichungen (BSGS):O(√m), benötigt zusätzlichen Speicher

Wichtige Sätze:

  • Satz von Bézout:Die Gleichung ax + my = ggT(a, m) hat immer ganzzahlige Lösungen
  • Kleiner Satz von Fermat:Wenn p eine Primzahl und ggT(a, p) = 1 ist, dann ist a^(p-1) ≡ 1 (mod p)
  • Satz von Euler:Wenn ggT(a, m) = 1 ist, dann ist a^φ(m) ≡ 1 (mod m)
  • Chinesischer Restsatz:Kann Systeme von Kongruenzen lösen