Pohlig–Hellman algorithm: Difference between revisions

Revision as of 16:59, 21 July 2005

Revision as of 17:00, 21 July 2005

Line 7:

'''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)\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^{\varphi(p)/p_1} & \equiv & (g^x)^{\varphi(p)/p_1} \pmod{p} \\