Pohlig-Hellman Algorithm

From Notes
Jump to navigation Jump to search

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 \beta \equiv \alpha^x \quad \iff \quad x \equiv L_{\alpha} \left( \beta \right) \pmod{p} \,\!}

We'll use 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 L_{\alpha}(\beta)} notation to represent this solution. Given the prime factorization of 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} ,

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 = \prod_i {q_i}^{r_i}}

We can solve 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}(\beta)\pmod{q^r}} for each 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}} (in other words, calculate 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 \pmod{q^r}} for each factor) and then recombine them using the Chinese remainder theorem to find 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} . Let's start by finding the 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} expansion of 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 x = d_0 + d_1 \, q + d_2 \, q^2 + \dots \,\!}

where each 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} is an integer digit between 0 and 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-1} . We can find the 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_0} through 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}} successively to find 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 \pmod{q^r}} . Let's multiply both sides of the equation above by 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}} :

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} 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{align}}

Where 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 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.

Retrieved from "https://notes.komputerwiz.net/w/index.php?title=Pohlig-Hellman_Algorithm&oldid=3053"