Revision as of 13:06, 21 March 2017 edit 145.116.47.254 (talk) explain why the worst-case complexity is O(sqrt(n)) ← Previous edit		Revision as of 13:08, 21 March 2017 edit undo 145.116.47.254 (talk) Since it applies to finite abelian groups, the algorithm has nothing to do with number theory. Also, fix sentence. Next edit →
Line 1: [[File:Pohlig-Hellman-Diagram.svg\|thumb\|350px\|alt=Pohlig Hellman Algorithm\|Steps of the Pohlig-Hellman algorithm.]] In [[~~number~~group theory]], the '''Pohlig–Hellman algorithm''', sometimes credited as the '''Silver–Pohlig–Hellman algorithm'''<ref name="Mollin06p344">[[#Mollin06\|Mollin 2006]], pg. 344</ref>, is a special-purpose [[algorithm]] for computing [[discrete logarithm]]s in a [[finite abelian group]] whose order is a [[smooth integer]]. The algorithm was discovered by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).

Pohlig–Hellman algorithm: Difference between revisions