# Solving DLP using the method of Pohlig-Hellman

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?

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}$$

$$2^{24} = 5 \pmod {101} ~~ \Large{\checkmark}$$
• Do you mean $29$ instead of $101$ ? Aug 26 '19 at 5:14
• @MaryStar: Which $101$ are you referring to? Looking at the problem, it looks totally different. Did an edit totally change the problem?