Pohlig-Hellman Algorithm

The Pohlig-Hellman algorithm is useful in finding the discrete logarithm $L_{\alpha }$ of a number and modulus. In other words, we wish to solve the following expression for $x$ .

\beta \equiv \alpha ^{x}\quad \iff \quad x\equiv L_{\alpha }\left(\beta \right){\pmod {p}}\,\!

We'll use the $L_{\alpha }(\beta )$ notation to represent this solution. Given the prime factorization of $p-1$ ,

p-1=\prod _{i}{q_{i}}^{r_{i}}

We can solve $L_{\alpha }(\beta ){\pmod {q^{r}}}$ for each ${q_{i}}^{r_{i}}$ (in other words, calculate $x{\pmod {q^{r}}}$ for each factor) and then recombine them using the Chinese remainder theorem to find $x$ . Let's start by finding the base- $q$ expansion of $x$ :

x=d_{0}+d_{1}\,q+d_{2}\,q^{2}+\dots \,\!

where each $d_{i}$ is an integer digit between 0 and $q-1$ . We can find the digits $d_{0}$ through $d_{r-1}$ successively to find $x{\pmod {q^{r}}}$ . Let's multiply both sides of the equation above by ${\tfrac {p-1}{q}}$ :

{\begin{aligned}x\,\left({\frac {p-1}{q}}\right)&=d_{0}\,\left({\frac {p-1}{q}}\right)+\left(p-1\right)\,\left(d_{1}+d_{2}\,q+d_{3}q^{2}+\dots \right)\\&=d_{0}\left({\frac {p-1}{q}}\right)+(p-1)\,N\end{aligned}}

Where $N$ is some integer. Let's raise each side of our original problem statement $\beta \equiv \alpha ^{x}{\pmod {p}}$ to the same ${\tfrac {p-1}{q}}$ power:

{\begin{aligned}\beta ^{\frac {p-1}{q}}&\equiv \left(\alpha ^{x}\right)^{\frac {p-1}{q}}{\pmod {p}}\\&\equiv \alpha ^{x\left({\frac {p-1}{q}}\right)}{\pmod {p}}\\&\equiv \alpha ^{d_{0}\,\left({\frac {p-1}{q}}\right)+\left(p-1\right)\,N}{\pmod {p}}\\&\equiv \alpha ^{d_{0}\,\left({\frac {p-1}{q}}\right)}\,{\cancel {\alpha ^{(p-1)N}}}{\pmod {p}}\\&\equiv \alpha ^{d_{0}\,\left({\frac {p-1}{q}}\right)}{\pmod {p}}\\\end{aligned}}

Note: That last cancellation was by Fermat's little theorem.

Now we just have to try possible values for $d_{0}$ until the following congruence works out:

\beta ^{\frac {p-1}{q}}\equiv \left(\alpha ^{\frac {p-1}{q}}\right)^{d_{0}}{\pmod {p}}\quad \quad d_{0}\in \{0,1,2,\dots ,q-1\}

Now that we know $d_{0}$ , we can find remaining digits (up to $d_{r-1}$ ) in succession. Notice by our original problem and our base expansion for $x$ that we have

{\begin{aligned}\beta &\equiv \alpha ^{x}{\pmod {p}}\\&\equiv \alpha ^{d_{0}+d_{1}\,q+d_{2}\,q^{2}+\dots }{\pmod {p}}\\&\equiv \alpha ^{d_{0}}\,\alpha ^{q\,(d_{1}+d_{2}\,q+d_{3}\,q^{2}+\dots )}{\pmod {p}}\\\beta \,\alpha ^{-d_{0}}&\equiv \alpha ^{q\,(d_{1}+d_{2}\,q+d_{3}\,q^{2}+\dots )}{\pmod {p}}\end{aligned}}

Now similar to what we did above, we can raise both sides to the ${\tfrac {p-1}{q^{k}}}$ power (notice $k=1$ in the first step) for $k$ up to $r$ (as $q^{r}$ is the highest prime power that divides $p-1$ ). In this case, we'll take $k=2$ :