Pohlig–Hellman algorithm: Difference between revisions

Revision as of 17:33, 17 June 2006

Revision as of 06:09, 2 August 2006

Line 1:

In mathematics, test 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_p which are coprime to p, and leave it to the advanced reader to extend the algorithm to other groups.