Diskrete Logarithmen - Pohlig-Hellman-Algorithmus

Der Pohlig-Hellman-Algorithmus, in der Literatur auch unter dem Namen "Silver-Pohlig-Hellman-Algorithmus" zu finden, berechnet für den diskreten Logarithmus den Wert x aus &alpha^x ≡ &beta Mod p.

p − 1 = ∏_i=1^kp_i^c_i


γ = α^(p−1)i/q Mod p für 0 ≤ i ≤ q − 1
β₀ := β

for j = 0, j ≤ c − 1 do

δ = β_j^(p−1)/qj+1
find i mit δ = γ
a _j:= i
β_j+1:= β_jα^−q_jqi