Pohlig–Hellman algorithm: Difference between revisions

Revision as of 07:37, 14 November 2021

Revision as of 15:11, 28 April 2022

Line 2:

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 introduced by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).{{cncitation needed|date=October 2020}}

== Groups of prime-power order ==

As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies to [[Group_Group (mathematics)|groups]] whose order is a [[prime power]]. The basic idea of this algorithm is to iteratively compute the <math>p</math>-adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.

(Note that for readability, the algorithm is stated for cyclic groups — in general, <math>G</math> must be replaced by the subgroup <math>\langle g\rangle</math> generated by <math>g</math>, which is always cyclic.)

Line 38:

==Complexity==

The worst-case input for the Pohlig–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 much 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==