Pohlig-Hellman Algorithm

The Pohlig-Hellman algorithm is useful in finding the discrete logarithm Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{\alpha}} of a number and modulus. In other words, we wish to solve the following expression for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta \equiv \alpha^x \pmod{p}} to the same Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{p-1}{q}} power:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

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

Now we just have to try possible values for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_0} until the following congruence works out:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_0} , we can find remaining digits (up to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{r-1}} ) in succession. Notice by our original problem and our base expansion for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} that we have

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Now similar to what we did above, we can raise both sides to the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{p-1}{q^k}} power (notice Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k = 1} in the first step) for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} up to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} (as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^r} is the highest prime power that divides Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} ). In this case, we'll take Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k=2} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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)} \pmod{p} \\ &\equiv \alpha^{d_1 \, \left( \frac{p-1}{q} \right) + (p-1) \, (d_2 + d_3 \, q + d_4 \, q^2 + \dots)} \pmod{p} \\ &\equiv \alpha^{d_1 \, \left( \frac{p-1}{q} \right) + (p-1) \, N} \pmod{p} \\ &\equiv \alpha^{d_1 \, \left( \frac{p-1}{q} \right)} \, \cancel{\alpha^{(p-1) \, N}} \pmod{p} \end{align}}

Once again, we reduced by Fermat's little theorem, and now we can try values for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_1} until we find the one that makes the equivalence work.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left( \beta \, \alpha^{-d_0} \right)^{\frac{p-1}{q^2}} \equiv \left( \alpha^{\frac{p-1}{q}} \right)^{d_1} \pmod{p} \quad \quad d_1 \in \{0,1,2,\dots,q-1\}}

---

Continue this process until we have all base Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q_r} digits Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_i} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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}} \pmod{p} \quad \quad d_{k-1} \in \{ 1, 2, \ldots, q-1 \}}

Now we know Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^r} .

Repeat this process for all prime factors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {q_i}^{r_i}} dividing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} , and then combine them with the Chinese remainder theorem.