Content deleted Content added
Tolly4bolly (talk | contribs) m Reverted 1 edit by 2A01:36D:1000:E55:4434:1A2F:54C:50AC identified as test/vandalism using STiki |
No edit summary |
||
Line 1:
[[File:Pohlig-Hellman-Diagram.svg|thumb|350px|alt=Pohlig Hellman Algorithm|Steps of the
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]].
Line 5:
== Groups of prime-power order ==
As an important special case, which is used as a subroutine in the general algorithm (see below), the
(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 21:
== The general algorithm ==
In this section, we present the general case of the
(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)
|