Das rechnerische Problem, einen Exponenten k in einer endlichen multiplikativen Gruppe G zu finden, sodass g^k = h für gegebene Basis g und Element h gilt; das Inverse der Potenzierung in dieser Gruppe.

Prinzip

Nutze die Gruppenstruktur: generische Algorithmen (Baby‑Step Giant‑Step, Pollard‑Rho) mit annähernd quadratischer Laufzeit in der Gruppenordnung sowie strukturabhängige Reduktionen (Pohlig–Hellman, Index‑Calculus), wenn die Gruppenordnung kleine Primfaktoren oder spezielle Form hat.

Demonstration

Beispiel in (Z/23Z)^×: g=5, h=8. Potenzen: 5^1=5, 5^2=2, 5^3=10, 5^4=4, 5^5=20, 5^6=8, daher k=6 und 5^6≡8 (mod 23).

Fehlanwendung

Algorithmen aufrufen, ohne sicherzustellen, dass g die betreffende Untergruppe erzeugt (ein Nicht‑Erzeuger liefert keine eindeutige Lösung), oder Index‑Calculus in Gruppen anwenden, für die er nicht effizient ist (z. B. bestimmte elliptische Kurven).

Konsequenz

Die (Un‑)Möglichkeit, diskrete Logarithmen effizient zu berechnen, bildet die Grundlage kryptographischer Primitive (Diffie‑Hellman, Signaturen) und bestimmt Sicherheitsparameter; effiziente Algorithmen zerstören die Sicherheit solcher Systeme.

Umkehrung

Potenzierung (g^k berechnen) ist die leichte Vorwärtsoperation; ihre Inversion (diskreter Logarithmus) ist typischerweise weit schwieriger, was die Asymmetrie zwischen Gruppenoperationen und ihren Inversen in der Komplexität hervorhebt.

Abgrenzung

Definiert für endliche multiplikative Gruppen oder zyklische Untergruppen; Komplexität und Methoden hängen von Gruppenordnung, Faktorisierung und Darstellung (endliche Körper, elliptische Kurven) ab; schließt kontinuierliche Gruppen und additive Modelle ohne passenden Isomorphismus aus.

Semantische Spannung

Spannung zwischen generischer Härte (Quadratwurzel‑Algorithmen) und Falllösbarkeit bei spezieller Struktur (glatte Ordnung, Index‑Calculus); praktische Sicherheit muss diese Gegensätze ausbalancieren.

Synthese

Die Berechnung des diskreten Logarithmus ist die Umkehrung der Potenzierung in endlichen Gruppen: ein algorithmisches Problem, dessen Lösbarkeit von der Gruppenstruktur abhängt und das durch eine Palette generischer und spezialisierter Algorithmen mit stark variierender Komplexität adressiert wird.