Pohlig–Hellman algorithm: Difference between revisions

Revision as of 05:02, 26 September 2016

Revision as of 05:27, 26 September 2016

Line 11:

:#Determine the prime factorization of the order of the group : <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-''p₁'' 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_1p} \\

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

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

\end{align}

</math></center><br> (using [[Euler's theorem]]). With everything else now known, we may try each value of ''b''₁ to see which makes the equation be true. If <math>g^{\varphi(p)/p_1} \not\equiv 1 \pmod{p_1p}</math>, then there is exactly one ''b''₁, and that ''b''₁ is the value of ''x'' modulo ''p''₁. (An exception arises if <math>g^{\varphi(p)/p_1} \equiv 1 \pmod{p_1p}</math> since then the order of ''g'' is less than φ(''p''). The conclusion in this case depends on the value of <math>e^{\varphi(p)/p_1} \mod p_1p</math> on the left: if this quantity is not 1, then no solution ''x'' exists; if instead this quantity is also equal to 1, there will be more than one solution for ''x'' less than φ(''p''), but since we are attempting to return only one solution ''x'', we may use ''b''₁=0.)

:#The same operation is now performed for ''p''₂ through ''p_n''.<br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p_i'' for the (''k''&nbsp;+&nbsp;1)st 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 either ''b''_''i'' or ''c''_''i'' the same way as before, depending on whether <math>g^{\varphi(p)/p_i} \equiv 1 \pmod{p_ip}</math>.

:# With all the ''b''_''i'' known, we have enough simultaneous [[congruence relation|congruence]]s to determine ''x'' using the [[Chinese remainder theorem]].