Pohlig–Hellman algorithm: Difference between revisions

Revision as of 21:10, 13 March 2008

Revision as of 15:45, 5 June 2008

Line 1:

In mathematics, the '''Pohlig-HellmanPohlig–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]].

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 by using [[Lagrange's_theorem_(group_theory)|Lagrange's Theorem]].

Line 23:

==References==

#S. Pohlig and M. Hellman. "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Trans. Information Theory 24, 1978, pp. 106-110106–110.