2
$\begingroup$

The prime number $p=67$ is given.

  • Show that $g=2$ is a generator of the group $\mathbb{Z}_p^{\star}$.
  • Compute the discrete logarithm of $y=3$ as for the base $g$ with Shanks-algorithm.
  • Compute the same discrete logarithm using the Pohlig–Hellman algorithm.

That's what I have tried:

  • $p-1=66=6 \cdot 11=2 \cdot 3 \cdot 11$

We know that $2^{66} \equiv 1 \mod{67}$. In order to show that $g=2$ is a generator of the group $\mathbb{Z}_p^{\star}$, it suffices to show that $2^{6}, 2^{22}, 2^{33} \not\equiv 1 \mod{67}$.

$$2^6=2^2 \cdot 2^2 \cdot 2^2=4 \cdot 4 \cdot 4=16 \cdot 4=64 \not\equiv 1 \mod{67}$$ $$2^{22}=2^{6} \cdot 2^{6} \cdot 2^6 \cdot 2^4=64 \cdot 64 \cdot 64 \cdot 16=4194304 \mod{67} \equiv 37 \mod{67} \not\equiv 1 \mod{67}$$ $$2^{33}=2^{22} \cdot 2^{11}=2^{22} \cdot 2^{6} \cdot 2^5=37 \cdot 64 \cdot 32 =75776\equiv 66 \mod{67}$$

  • Let $m= \lceil \sqrt{67}\rceil=9$. We compute the values $1, g, g^2, \dots, g^8$. $$g^0=1\\ g^1=2 \\ g^2=4 \\ g^3=8\\ g^4=16 \\ g^5=32 \\ g^6=64 \\ g^7=61 \\ g^8=58$$

    Now we compute $g^{-m}=2^{-9}=(2^{-1})^9$

    $$67=2 \cdot 33+1 \Rightarrow 1=67-2 \cdot 33$$

    So the inverse of $2$ modulo $67$ is $-33 \equiv 34 \mod {67}$.

    $g^{-m}=(2^{-1})^9=34^9=34^2 \cdot 34^2 \cdot 34^2 \cdot 34^2 \cdot 34 \equiv 17 \cdot 17 \cdot 17 \cdot 17 \cdot 34 \equiv 53 \mod{67}$

    Now we start computing $y(g^{-m})^q=3 \cdot 53^q$ for increasing values of $q$.

    $y (g^{-m})^0=3 \cdot 53^0=3 \\ y (g^{-m})^1=3 \cdot 53^1=159 \equiv 25 \mod{67}\\ y (g^{-m})^2=3 \cdot 53^2=8427 \equiv 52\mod{67} \\ y (g^{-m})^3=3 \cdot 53^3 \equiv 9 \mod{67} \\ y (g^{-m})^4 \equiv 8 \mod{67} $

    We have $g^3=y(g^{-m})^4 \Rightarrow y=g^{3+4m}=g^{3+4 \cdot 9}=g^{39}$

    So $39$ is the dicrete logarithm we seek.

Is it right so far?

  • $p-1=66=2 \cdot 3 \cdot 11$

    We want to determine the numbers $x_1 \equiv x \mod{2}, x_2 \equiv x \mod{3}, x_3 \equiv x \mod{11}$. Could you explain me how we could determine them? I haven't understood the general idea.

$\endgroup$

1 Answer 1

0
$\begingroup$

Let's write $y\equiv g^x\bmod{p}$, so that the goal is to find $x$. By exponentiating both sides we have the equalities \begin{align*} y^{33}\equiv (g^{33})^{x}\bmod{p}, \\ y^{22}\equiv (g^{22})^{x}\bmod{p}, \\ y^{6}\equiv (g^{6})^{x}\bmod{p}. \end{align*} Note that $g^{33}$, $g^{22}$ and $g^{6}$ have respective orders $2$, $3$ and $11$. Hence solving these three equalities gives $x\bmod{2}$, $x\bmod{3}$ and $x\bmod{11}$. Now use the Chinese Remainder Theorem to get $x\bmod{66}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .