Pohlig-Hellman Algorithm
Pohlig-Hellman zerlegt einen diskreten Logarithmus in einer Gruppe glatter Ordnung in diskrete Logarithmen in jeder Untergruppe von Primzahlpotenz-Ordnung und führt sie dann mit dem CRT zusammen.
Zweck
Beschleunigt diskrete Logarithmen in Gruppen glatter Ordnung und leitet die Wahl sicherer Gruppenparameter.
Mechanismus
Ist die Gruppenordnung n=∏p_i^e_i, so löst man x mod p_i^e_i einzeln (mit BSGS in der Untergruppe der Ordnung p_i^e_i) und führt sie mit dem CRT zusammen. DH-Parameter sollten daher eine Ordnung mit großem Primfaktor besitzen.
Anwendungsfälle
- Beschleunigung diskreter Logarithmen
- DH-Parametersicherheit
- Kryptoanalyse