|
In [[number theory]], the '''Pohlig–Hellman algorithm''' is a [[special-purpose]] [[algorithm]] for computing [[discrete logarithm]]s in a [[multiplicative group]] whose order is a [[smooth integer]]. The algorithm is based on the [[Chinese remainder theorem]].
The algorithm was discovered by Roland Silver, but first published by [[Stephen Pohlig]] and [[Martin Hellman]] (independent of Silver).
We will explain the algorithm inas termsit ofapplies to the group formed'''Z'''<sup>*</sup><sub>''p''</sub> byconsisting takingof all the elements of '''Z'''<sub>''p''</sub> which are [[coprime]] to ''p'', and leave it to the advanced reader to extend the algorithm to other groups by using [[Lagrange's theorem (group theory)|Lagrange's theorem]].
:'''Input''' Integers ''p'', ''g'', ''e''.
:'''Output''' An Integer ''x'', such that ''e'' ≡ ''g''<sup>''x''</sup> (mod ''p'') (if one exists).
:#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''<sub>''i''</sub> 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''<sub>1</sub> divides this order but ''p''<sub>1</sub><sup>2</sup> does not. Then we knowneed to determine ''x'' mod ''p''<sub>1</sub>, that is, we need to know the ending coefficient ''b''<sub>1</sub> in the base-''b'' expansion of ''x'', i.e. in the expansion ''x'' = ''a''<sub>1</sub> ''p''<sub>1</sub> + ''b''<sub>1</sub>. We nowcan find the value of ''b<sub>1</sub>'' forby whichexamining all the followingpossible values between 0 and ''p''<sub>1</sub>-1. (We equationmay holdsalso usinguse a fastfaster algorithm such as [[baby-step giant-step]] in some cases.) 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} \\
& \equiv (g^{\varphi(p)/p_1})^{b_1} \pmod{p}
\end{align}
</math></center><br> (using [[Euler's theorem]]). With everything else now known, we may try each value of ''b''</centersub>1<br/sub>Note to see which makes the equation be true; precisely one will work, and that ''b''<sub>1</sub> is the value of ''x'' modulo ''p''<sub>1</sub>. (An exception arises if <math>g^{\varphi(p)/p_1} \equiv 1 \pmod{p}</math> since then the order of ''g'' is less than φ(''p''). andThe conclusion in this case depends on the value of <math>e^{\varphi(p)/p_1} \mod p</math> muston bethe left: if this quantity is not 1, forthen ano solution to''x'' exist.exists; Inif instead this casequantity is also equal to 1, there will be more than one solution for ''x'' less than φ(''p''), but since we are notattempting lookingto forreturn theonly wholeone setsolution ''x'', we canmay require thatuse ''b''<sub>1</sub>=0.)<br><br>
:#The same operation is now performed for ''p''<sub>2</sub> up tothrough ''p<sub>n</sub>''.<br><br>A minor modification is needed where a prime number is repeated. Suppose we are seeing ''p<sub>i</sub>'' for the (''k'' + 1)thst time. Then we already know ''c<sub>i</sub>'' in the equation ''x'' = ''a''<sub>''i''</sub> ''p''<sub>''i''</sub><sup>''k''+1</sup> + ''b''<sub>''i''</sub> ''p''<sub>''i''</sub><sup>''k''</sup> + ''c''<sub>''i''</sub>, and we find ''b''<sub>''i''</sub>'' the same way as before. <br>
:#We endWith upall withthe ''b''<sub>''i''</sub> known, we have enough simultaneous [[congruence relation|congruence]]s soto thatdetermine ''x'' can be solved using the [[Chinese remainder theorem]].
==Complexity==
| 