Löser für den diskreten Logarithmus

Das Problem des diskreten Logarithmus fragt nach einer ganzen Zahl x, sodass eine gegebene Basis g hoch x kongruent zu einem Ziel h modulo einer Primzahl p ist. Es liegt dem Diffie-Hellman-Schlüsselaustausch, der ElGamal-Verschlüsselung und vielen Lehrbuchaufgaben der algebraischen Kryptografie zugrunde. Diese Fähigkeit setzt den klassischen Babystep-Giantstep-Algorithmus um: eine deterministische Suche in Wurzelzeit, die entweder den kleinsten nichtnegativen Exponenten findet oder beweist, dass h keine Potenz von g in der multiplikativen Gruppe modulo p ist.

Wonach der diskrete Logarithmus fragt

Für gegebene ganze Zahlen g, h und p ist der diskrete Logarithmus von h zur Basis g modulo p jede ganze Zahl x, die g hoch x kongruent zu h modulo p erfüllt. Wenn eine Lösung existiert, ist der kleinste nichtnegative Vertreter im Bereich null bis p minus zwei eindeutig, sobald Sie diesen Bereich festlegen, und er ist der Wert, den dieses Werkzeug zurückgibt.

Anders als bei gewöhnlichen reellen Logarithmen gibt es keine geschlossene elementare Formel, die für beliebige Primzahlen funktioniert; die Schwierigkeit, x für sorgfältig gewählte große Primzahlen zu ermitteln, ist genau der Grund, warum Kryptografie mit diskretem Logarithmus nützlich ist. In der Lehre und bei Experimenten mit kleinen Parametern brauchen Sie dennoch einen korrekten, überprüfbaren Löser: einen, der die Primzahlhypothese validiert, die Eingaben in das kanonische Restsystem reduziert, systematisch sucht und entweder einen verifizierbaren Exponenten ausgibt oder klar feststellt, dass keine Lösung existiert.

Das ist der Vertrag dieses Endpunkts: reine modulare Arithmetik, keine Heuristiken und keine Netzwerkaufrufe.

Wie Babystep-Giantstep x findet

Babystep-Giantstep schreibt den unbekannten Exponenten als x gleich i mal m plus j um, wobei m etwa die Quadratwurzel der Gruppenordnung p minus eins ist und sowohl i als auch j von null bis m laufen. Der Algorithmus speichert zunächst jeden Baby-Wert g hoch j modulo p in einer Hash-Map, die nach dem Rest indiziert ist, und schreitet dann in Giantsteps voran, indem er das Ziel wiederholt mit dem modularen Inversen von g hoch m multipliziert und jeden Zwischenrest in der Map nachschlägt.

Ein Treffer liefert sowohl i als auch j und damit x. Basen und Ziele außerhalb von null bis p minus eins werden modulo p reduziert, und die Antwort gibt die reduzierten g, h und p zurück, sodass Aufrufende genau die gelöste Instanz nachvollziehen können.

Eingaben, Grenzen, Preise und wann es keine Lösung gibt

Pflichtfelder sind g (Basis), h (Zielrest) und p (Primmodul). Ziffernzeichenketten werden für große ganze Zahlen innerhalb der Modulgrenze akzeptiert. Liegt h nicht in der von g modulo p erzeugten zyklischen Untergruppe — etwa wenn g nur eine echte Untergruppe erzeugt und h außerhalb davon liegt — gibt der Löser solved false mit einem null-Exponenten und einer erklärenden Meldung zurück, statt ein falsches x zu erfinden.

Dieses Ergebnis ist eine erfolgreiche Berechnung, kein Client-Fehler, denn die Eingabe war wohlgeformt und die mathematische Antwort lautet, dass kein Logarithmus existiert. Client-Fehler umfassen fehlende Felder, Nicht-Ganzzahlen, Moduln außerhalb des erlaubten Bereichs und zusammengesetztes p. Nutzen Sie das Ergebnis, um Hausaufgaben zu prüfen, Bekanntantwort-Tests für Kryptobibliotheken zu erzeugen oder die Untergruppenzugehörigkeit zu erkunden, bevor Sie Parameter in einem echten Protokollentwurf hochskalieren.