Pohlig–Hellman algorithm: Difference between revisions

Revision as of 06:40, 21 August 2006

Revision as of 12:22, 28 August 2006

Line 4:

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

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

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

Line 12:

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

\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 &phi;φ(''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 &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 [[congruence|congruences]] so that ''x'' can be solved using the [[Chinese remainder theorem]].