Pohlig–Hellman algorithm: Difference between revisions

Revision as of 11:02, 19 September 2011

Revision as of 11:08, 8 November 2011

Line 9:

:#Determine the prime factorization of the order of the group (the [[totient]] in this case) : <br><center><math>\varphi(p)= p_1\cdot p_2 \cdots p_n</math></center> (All the ''p''_''i'' are considered small since the group order is smooth.)

:#From the [[Chinese remainder theorem]] it will be sufficient to determine the values of ''x'' modulo each prime power dividing the group order. Suppose for illustration that ''p''₁ divides this order but ''p''₁² does not. Then we need to determine ''x'' mod ''p''₁, that is, we need to know the ending coefficient ''b''₁ in the base-''bp₁'' expansion of ''x'', i.e. in the expansion ''x'' = ''a''₁ ''p''₁ + ''b''₁. We can find the value of ''b₁'' by examining all the possible values between 0 and ''p''₁-1. (We may also use a faster algorithm such as [[baby-step giant-step]] when the order of the group is prime.<ref name="Menezes97p109">[[#Menezes97|Menezes, et. al 1997]], pg. 109</ref>) The key behind the examination is that:<br> <center><math>

\begin{align}e^{\varphi(p)/p_1} & \equiv (g^x)^{\varphi(p)/p_1} \pmod{p} \\

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