Pohlig–Hellman algorithm: Difference between revisions

Revision as of 23:27, 2 February 2008

Revision as of 03:48, 8 March 2008

Line 6:

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

:#UseDetermine the prime factorization and [[Euler's totient function]] to determine the prime factorization of the order of the group : <br><center><math>\varphi(p)= p_1\cdot p_2 \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^{\varphi(p)/p_1} & \equiv & (g^x)^{\varphi(p)/p_1} \pmod{p} \\