Pohlig–Hellman algorithm: Difference between revisions

Revision as of 22:51, 4 July 2005

Revision as of 13:12, 9 July 2005

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

'''Input''' Integers ''p'', ''g'', ''e''.

'''Output''' Integer ''x'', such that ''e = g^x (mod p)''.

'''Algorithm''' Use [[Euler's phi function]] to determine the prime factorization of the order of the group :

<math>\phi(p)=p_0\cdot p_1 \cdot \ldots \cdot p_n</math>

From the remainder theorem we know that ''x = a₁ p₁ + b₁''. We now find the value of b₁ for which the following equation holds :

<math>\begin{matrix}e^{\phi(p)/p_1} & = & (g^x)^{\phi(p)/p_1} \pmod{p} \\

& = & g^{\phi(p)}g^{b_1\phi(p)/p_1} \pmod{p} \\

& = & g^{b_1\phi(p)/p_1} \pmod{p}

\end{matrix}

</math> (using [[Euler's theorem]])

The same operation is now performed for ''p₂'' up to ''p_n''.

A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p_i'' for the ''k+1''-th time. Then already know ''c_i'' in the equation ''x = a_i p_i^k+1 + b_ip_i^k+c_i'', and we find ''b_i'' the same way as before.

We end up with enough simulatious congruencies so that ''x'' can be solved using the [[Chinese remainder theorem]].

{{math-stub}}