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

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.