2
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Thanks a lot!! :-) $\endgroup$
    – Mary Star
    Jun 14 '19 at 21:41
  • $\begingroup$ Do you mean $29$ instead of $101$ ? $\endgroup$
    – Mary Star
    Aug 26 '19 at 5:14
  • $\begingroup$ @MaryStar: Which $101$ are you referring to? Looking at the problem, it looks totally different. Did an edit totally change the problem? $\endgroup$
    – Moo
    Aug 26 '19 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.