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⟺x\equiv L_{\alpha }\left(\beta \right)(\mathrm{mod}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 )(\mathrm{mod}{q}^r)$ for each ${q_i}^{r_i}$ (in other words, calculate $x(\mathrm{mod}{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(\mathrm{mod}{q}^r)$. Let's multiply both sides of the equation above by $\frac{p-1}{q}$:

$\begin{array}{rl}x\left(\frac{p-1}{q}\right)& =d_0\left(\frac{p-1}{q}\right)+(p-1)(d_1+d_{2}q+d_3{q}^2+\dots )\\ & =d_0\left(\frac{p-1}{q}\right)+(p-1)N\end{array}$

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

$\begin{array}{rl}{\beta }^{\frac{p-1}{q}}& \equiv {\left({\alpha }^x\right)}^{\frac{p-1}{q}}(\mathrm{mod}p)\\ & \equiv {\alpha }^{x\left(\frac{p-1}{q}\right)}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_0\left(\frac{p-1}{q}\right)+(p-1)N}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_0\left(\frac{p-1}{q}\right)}\cancel{{\alpha }^{(p-1)N}}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_0\left(\frac{p-1}{q}\right)}(\mathrm{mod}p)\\ \end{array}$

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}(\mathrm{mod}p)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{array}{rl}\beta & \equiv {\alpha }^x(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_0+d_{1}q+d_2{q}^2+\dots }(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_0}{\alpha }^{q(d_1+d_{2}q+d_3{q}^2+\dots )}(\mathrm{mod}p)\\ \beta {\alpha }^{-d_0}& \equiv {\alpha }^{q(d_1+d_{2}q+d_3{q}^2+\dots )}(\mathrm{mod}p)\end{array}$

Now similar to what we did above, we can raise both sides to the $\frac{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$:

$\begin{array}{rl}{\left(\beta {\alpha }^{-d_0}\right)}^{\frac{p-1}{q^2}}& \equiv {\left({\alpha }^{q(d_1+d_{2}q+d_3{q}^2+\dots )}\right)}^{\frac{p-1}{q^2}}\\ & \equiv {\alpha }^{\frac{p-1}{q}(d_1+d_{2}q+d_3{q}^2+\dots )}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_1\left(\frac{p-1}{q}\right)+(p-1)(d_2+d_{3}q+d_4{q}^2+\dots )}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_1\left(\frac{p-1}{q}\right)+(p-1)N}(\mathrm{mod}p)\\ & \equiv {\alpha }^{d_1\left(\frac{p-1}{q}\right)}\cancel{{\alpha }^{(p-1)N}}(\mathrm{mod}p)\end{array}$

Once again, we reduced by Fermat's little theorem, and now we can try values for $d_1$ until we find the one that makes the equivalence work.

${\left(\beta {\alpha }^{-d_0}\right)}^{\frac{p-1}{q^2}}\equiv {\left({\alpha }^{\frac{p-1}{q}}\right)}^{d_1}(\mathrm{mod}p)d_1\in \{0,1,2,\dots ,q-1\}$

---

Continue this process until we have all base $q_r$ digits $d_i$ for $x$.

${\left(\beta \prod _{i=0}^{\text{known}}{\alpha }^{-d_i{q}^i}\right)}^{\frac{p-1}{q^k}}\equiv {\left({\alpha }^{\frac{p-1}{q}}\right)}^{d_{k-1}}(\mathrm{mod}p)d_{k-1}\in \{1,2,\dots ,q-1\}$

Now we know $x$ mod $q^r$.

Repeat this process for all prime factors ${q_i}^{r_i}$ dividing $p-1$, and then combine them with the Chinese remainder theorem.