Pohlig–Hellman algorithm: Difference between revisions

Revision as of 13:08, 21 March 2017

Revision as of 13:20, 24 March 2017

Line 1:

[[File:Pohlig-Hellman-Diagram.svg|thumb|350px|alt=Pohlig Hellman Algorithm|Steps of the Pohlig-Hellman algorithm.]]

In [[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).

Line 20:

==Complexity==

The worst-case input for the Pohlig-HellmanPohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the [[Baby-step giant-step|Baby-step giant-step algorithm]], hence the worst-case time complexity is <math>\mathcal O(\sqrt n)</math>. However, it is more efficient if the order is smooth: Specifically, if <math>\prod_i p_i^{e_i}</math> is the prime factorization of <math>n</math>, then the algorithm's complexity is <math display="block">\mathcal O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right)</math> group operations.<ref name="Menezes97p108">[[#Menezes97|Menezes, et. al 1997]], pg. 108</ref>

==Notes==