Pohlig–Hellman algorithm: Difference between revisions

Content deleted Content added
clarify we are talking about group operations; improve formatting
Nothing about this algorithm is specific to multiplicative groups of finite fields.
Line 1:
[[File:Pohlig-Hellman-Diagram.svg|thumb|350px|alt=Pohlig Hellman Algorithm|Steps of the Pohlig-Hellman algorithm.]]
In [[number 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 [[multiplicativefinite 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 time complexity of the Pohlig–Hellman algorithm is <math>\mathcal O(\sqrt n)</math> for a group of order <math>n</math> but 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 complexity can be stated as <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>
<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==