Revision as of 14:38, 30 July 2008 edit CRGreathouse (talk \| contribs) Autopatrolled, Administrators 13,002 edits complexity, attribution ← Previous edit		Revision as of 13:34, 2 December 2008 edit undo Icmpecho (talk \| contribs) 4 edits m p is not the order of the group. The totient is. Next edit →
Line 8: :'''Output''' Integer ''x'', such that ''e ≡ g<sup>x</sup> (mod p)''. :#Determine the prime factorization ~~and [[totient]]~~ of the order of the group (the [[totient]] in this case) : <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<sub>1</sub> p<sub>1</sub> + b<sub>1</sub>''. We now find the value of ''b<sub>1</sub>'' 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} \\

Pohlig–Hellman algorithm: Difference between revisions