Content deleted Content added
No edit summary |
the general case is analogous except that Lagrange's theorem is used rather than Euler's |
||
Line 1:
In mathematics, the '''Pohlig-Hellman algorithm''' is an [[algorithm]] for the computation of [[discrete logarithm]]s in a [[multiplicative group]] whose order is a [[smooth integer]]. The algorithm is based on the [[Chinese remainder theorem]] and runs in [[polynomial time]].
We will explain the algorithm in terms of the group formed by taking all the elements of Z<sub>p</sub> which are coprime to p, and leave it to the advanced reader to extend the algorithm to other groups by using [[Lagrange's_theorem_(group_theory)|Lagrange's Theorem]].
:'''Input''' Integers ''p'', ''g'', ''e''.
| |||