Computation of discrete logarithm

[evinda]

Hello! (Wave)

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.
  

 

[jvicens]

Hi there! Yes, your approach so far is correct. To determine the numbers $x_1, x_2, x_3$, we use the Chinese Remainder Theorem. This theorem states that for a system of congruences $x \equiv a \mod{m}$ and $x \equiv b \mod{n}$, where $m$ and $n$ are relatively prime, there exists a unique solution modulo $mn$.

In our case, we have $x \equiv x_1 \mod{2}, x \equiv x_2 \mod{3}, x \equiv x_3 \mod{11}$. Using the Chinese Remainder Theorem, we can find $x$ by solving the following system of congruences:

$$x \equiv 1 \mod{2}, x \equiv 0 \mod{3}, x \equiv 0 \mod{11}$$

We can solve this system by finding the smallest positive integer solution to $x \equiv 1 \mod{2}$, which is $x=1$, and the smallest positive integer solution to $x \equiv 0 \mod{3}$, which is $x=3$, and the smallest positive integer solution to $x \equiv 0 \mod{11}$, which is $x=11$. Therefore, our solution for $x$ is $x=11$.

Using this approach, we can find $x_1=1, x_2=3,$ and $x_3=11$. I hope this helps! Let me know if you have any other questions.