Pohlig–Hellman algorithm: Difference between revisions

Revision as of 15:45, 5 June 2008

Revision as of 14:38, 30 July 2008

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]].

The algorithm was discovered by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).

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 13 ⟶ 15:

\end{matrix}

</math> (using [[Euler's theorem]])</center><br>Note that if <math>g^{\varphi(p)/p_1} \equiv 1 \pmod{p}</math> then the order of ''g'' is less than φ(''p'') and <math>e^{\varphi(p)/p_1} \mod p</math> must be 1 for a solution to exist. In this case there will be more than one solution for ''x'' less than φ(''p''), but since we are not looking for the whole set, we can require that ''b''₁=0.<br><br>The same operation is now performed for ''p₂'' up to ''p_n''.<br><br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p_i'' for the ''k+1''-th time. Then we already know ''c_i'' in the equation ''x = a_i p_i^k+1 + b_i p_i^k+c_i'', and we find ''b_i'' the same way as before.

:#We end up with enough simultaneous [[congruence|congruences]]s so that ''x'' can be solved using the [[Chinese remainder theorem]].

==Complexity==

The time complexity of the Pohlig–Hellman algorithm is <math>O(\sqrt n)</math> for a group of order ''n'', but it is more efficient if the order is smooth.

==References==

#S. Pohlig and M. Hellman. "[http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance]", ''IEEE Trans.Transactions on Information Theory'' '''24,''' (1978), pp. 106–110.

{{Numtheory-stub}}

Line 21 ⟶ 29:

[[pl: Redukcja Pohliga-Hellmana]]

[[ru: Алгоритм Полига-Хеллмана]]

==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–110.