##  [Berechnung Diskreter Logarithmen](/de/node/62925) 

 Definition

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

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

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

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

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

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

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

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

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.