Solving DLP using the method of Pohlig-Hellman

Question

I want to solve the DLP for $p=29$, $a=2$ and $b=5$ using the method of Pohlig-Hellman.

$$$$

I have done the following:

We have that $p-1=28=2^2\cdot 7$.

We get \begin{align*}&x_2= x\pmod {2^2} \\ &x_7=x\pmod 7\end{align*}

$x_2$ is a number $\mod 4$, so $x_2=c_0+c_1(2)$ with coefficients $0$ or $1$.

We have that \begin{equation*}b^{\frac{p-1}{2}}=5^{14}\equiv 1\end{equation*}

Since this is equal to $a^{c_0\cdot \frac{p-1}{2}}$ we have that $c_0=0$.

We divide $b$ by $a^{c_0}=1$ and we get $b\cdot a^{-c_0}=b=5$.

We have that $5^{\frac{p-1}{4}}=5^7\equiv 28$.

Since this is equal to $a^{c_1\cdot \frac{p-1}{2}}$ we have that $c_1=1$.

Therefore, $x_2=c_0+c_1(2)=1$.

$x_7$ is a number $\pmod 7$.

So, $x_7=c_0$ with $c_0\in \{0,\ldots , 6\}$.

We have that $b^{\frac{p-1}{7}}=5^4\equiv 16$.

This this is equal to $a^{c_0\cdot \frac{p-1}{7}}=2^{4c_0}$ we have that $c_0=1$.

So $x_7=c_0(7)=1$.

We use the Chinese theorem for the system \begin{align*}x=1\pmod 4 \\ x=1\pmod 7\end{align*} Solving this one we get that $x\equiv 1$.

Is everything correct?

Answer 1

As a guide, we will use the MSE post - Pohlig-Hellman Algorithm for solving a DLP - can $x_0$ have > 1 solution?.

A description of the algorithm can be found in

• $(1)$ A Course in Number Theory and Cryptography, 2nd Ed., N. Koblitz
• $(2)$ An Introduction to Mathematical Cryptography, J. Hoffstein, J. Pipher, J. H. Silverman
• $(3)$ Number Theory for Computing, 2nd Ed., S. Y. Yan
• $(4)$ An Introduction to Cryptography, R. A. Mollin

We will use the Pohlig-Hellman algorithm to solve a Discrete Log Problem to find $x$ in

$$2^x = 5 \pmod{101}$$

Using the notation from $(2)$

$$g^x = h \pmod p$$

We have

$$g = 2, h = 5, p = 101, N = p - 1 = 100 = \prod_{i=1}^{n} q_i^{e_i} = q_1^{e_1} \cdot q_2^{e_2} = 2^2 \cdot 5^2 $$

We can summarize the necessary algorithm calculations in a handy table as

$$\begin{array}{|c|c|c|c|c|} \hline \large q & \large e & \large g^{(p-1)/q^e} & \large h^{(p-1)/q^e} & \mbox{Solve}~ \large \left(g^{(p-1)/q^e} \right)^x = ~ \large h^{(p-1)/q^e}~ \mbox{for} ~ \large x \\ \hline 2 & 2 & 10 & 1 & \mbox{Calculation I = ?}\\ \hline 5 & 2 & 16 & 19 & \mbox{Calculation II = ?}\\ \hline \end{array}$$

Calculation I: Solve

$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {2^2} \equiv x_0 + 2x_1 \pmod {2^2}$$

• Solve $(10)^x = 1 \pmod {101}$ for $x_0, x_1$.
• $x_0: (10^{2^1})^{x_0} = 100^{x_0} = 1^{2^1} \pmod {101} \implies (100)^{x_0} = 1 \pmod{101} \implies x_0 = 2$
• $x_1: (10^{2^1})^{x_1} = 100^{x_1} = (1 \times 10^{-x_0})^{2^0} \pmod {101} \implies (100)^{x_1} = 100 \pmod{101} \implies x_1 = 1$

Our first result is

$$x \equiv x_0 + 2 x_1 \pmod {2^2} \equiv 2 + 2 \pmod {2^2} \equiv 0 \pmod {2^2}$$

Calculation II: Solve

$$x \equiv x_0 + x_1q + \ldots + x_{e-1}q^{e−1} \pmod {5^2} \equiv x_0 + 5 x_1 \pmod {5^2}$$

• Solve $(16)^x = 19 \pmod {101}$ for $x_0, x_1$.
• $x_0: (16^{5^1})^{x_0} = 95^{x_0} = 19^{5^1} \pmod {101} = 84 \pmod{101} \implies x_0 = 4$.
• $x_1: (16^{5^1})^{x_1} = 95^{x_1} = (19 \times 16^{-x_0})\pmod{101} = (19 \times 16^{-4})\pmod{101} = (19 \times 31)\pmod{101} = 84\pmod{101} \implies x_1 = 4$

Our second result is

$$x \equiv x_0 + 5 x_1 \pmod {5^2} \equiv 24 \pmod {5^2}$$

Next, use the Chinese Remainder Theorem to solve the simultaneous congruence's

$$x \equiv 0 \pmod {2^2} , ~~ x \equiv 24\pmod {5^2}$$

The result is

$$x \equiv 24 \pmod{2^2 \times 5^2}$$

Check the answer

$$2^{24} = 5 \pmod {101} ~~ \Large{\checkmark}$$