Pohlig–Hellman algorithm: Difference between revisions

Revision as of 02:58, 13 July 2005

Revision as of 16:59, 21 July 2005

Line 5:

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

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

#Use [[Euler's phitotient function]] to determine the prime factorization of the order of the group : <br><center><math>\phivarphi(p)=\equiv p_0\cdot p_1 \cdot \ldots \cdot p_n</math></center>

#From the remainder theorem we know that ''x = a₁ p₁ + b₁''. We now find the value of ''b₁'' for which the following equation holds using a fast algorithm such as [[Baby-step giant-step]] :<br> <center><math>

\begin{matrix}e^{\phivarphi(p)/p_1} & =\equiv & (g^x)^{\phivarphi(p)/p_1} \pmod{p} \\

& =\equiv & (g^{\phivarphi(p)})^{a_1}g^{b_1\phivarphi(p)/p_1} \pmod{p} \\

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

\end{matrix}

</math> (using [[Euler's theorem]])</center><br>Note that if <math>g^{\phivarphi(p)/p_1} =\equiv 1 \pmod{p}</math> then the order of ''g'' is less than ø&phi;(''p'') and <math>e^{\phivarphi(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 ø&phi;(''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 congruences so that ''x'' can be solved using the [[Chinese remainder theorem]].