Pohlig–Hellman algorithm: Difference between revisions

Content deleted Content added
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 Pohlig-HellmanPohlig–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]].
 
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 Pohlig-HellmanPohlig–Hellman algorithm applies to [[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 21:
 
== The general algorithm ==
In this section, we present the general case of the Pohlig-HellmanPohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the [[Chinese remainder theorem]] (to combine these to a logarithm in the full group).
 
(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.)