Content deleted Content added
m Reverted edits by 180.254.30.192 (talk) to last version by Sadeq |
→Groups of prime-power order: added link |
||
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-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.)
| |||