Apply Pohling-Hellman to calculate the discrete logarithm

96 Views Asked by At

I am looking at the following example of calculating the discrete logarithm with Pohli-Hellman. The group is $\mathbb{F}_{29}^{\times}$ and we given $y=10$ and $g=3$. We want to find $0 \leq x \leq 28$ such that $y=g^x \pmod {29}$.

I have done the following:

The order of the group is $28=2^2 \cdot 7$.

  • $10^{2^2}=\left (3^{2^2}\right )^x \Rightarrow 10^4=(3^4)^x \Rightarrow 24=23^x$

    To find $x$ we do the following:

    $$23^0=1 \\ 23^1=23 \\ 23^2=7 \\ 23^3=-13 \\ 23^4=20 \\ 23^5=-4 \\ 23^24$$

    So, $x \equiv 6 \pmod 4 \Rightarrow x \equiv 2 \pmod 4$.

  • $10^7=\left (3^7\right )^x \Rightarrow 17=12^x$

    To find $x$ we do the following:

    $$12^0=1 \\ 12^1=12 \\ 12^2=28 \\ 12^3=17$$

    So, $x \equiv 3 \pmod 7$.

We have $$x \equiv 2 \pmod 4 \\ x \equiv 3 \pmod 7$$

From Chinese remainder theorem we get the following:

$$x=7 \cdot 2 \cdot s_1+3 \cdot 4 \cdot s_2$$

$$7s_1 \equiv 1 \pmod 4 \Rightarrow s_1=3\\ 4s_2 \equiv \pmod 7 \Rightarrow s_2=2$$

That means that $x=42+24=66 \equiv 12 \pmod {29}$.

But in my notes the result is $x=27$. What have I done wrong??