Shank's Baby-Step Giant-Step for $3^x \equiv 2 \pmod{29}$

Question

Problem: Solve $3^x \equiv 2 \pmod{29}$ using Shank's Baby-Step Giant-Step method.

I choose $k=6$ and calculated $3^i \pmod {29}$ for $i=1,2,...,6$. $$3^1 \equiv 3 \pmod {29}$$ $$3^2 \equiv 9 \pmod {29}$$ $$3^3 \equiv 27 \pmod {29}$$ $$3^4 \equiv 23 \pmod {29}$$ $$3^5 \equiv 11 \pmod {29}$$ $$3^6 \equiv 4 \pmod {29}$$

Then I have calculated $3^{-1} \equiv 10 \pmod {29}$ and started calculating second list:

$$2 \cdot 3^{-6} \equiv 2 \cdot 10^6 \equiv 2 \cdot 22 = 44 \equiv 15 \pmod {29}$$ $$2 \cdot 3^{-12} \equiv 2 \cdot {3^{-6}}^2 \equiv 2 \cdot 15^2 \equiv 2 \cdot 22 = 44 \equiv 15 \pmod {29}$$ $$2 \cdot 3^{-18} \equiv 2 \cdot {3^{-12}}^2 \equiv 2 \cdot 22^2 \equiv 2 \cdot 20 = 40 \equiv 11\pmod {29}$$

And now I can stop. I can see that: $$ 3^5 \equiv 11 \pmod {29}\ and\ 2 \cdot 3^{-18} \equiv 11 \pmod {29}$$ Therefore $x = 5 + 18 = 23$

But when I plugin $x=23$ above I get that $3^{23} \equiv 8 \pmod {29}$. So where am I wrong?

Answer 1

I found flaw in my calculus for the second expression in second list, it should be

$$ 2 \cdot 3^{-12} = 2 \cdot (3^{-6})^2 \equiv 2 \cdot 22^2 = 2 \cdot 484 \equiv 11 \pmod {29}$$

Hence, $x = 5 + 12 = 17 $ which is correct.

Answer 2

$$3^x \equiv 2 (\text{ mod } 29)$$ $\varphi(29) = 28$
$m = \lceil \sqrt{28} \rceil = 6$

$\begin{array}{c|ccccc} j& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 3^j & 1 & 3& 9 & 27 & 23 & \color{#f00}{11} \end{array}$

$3^{-6}= 3^{28 -6 } = 3^{22} = 22$

$\begin{array}{c|ccccc} i & 0 & 1 & 2\\ \hline 2\cdot 22^i & 2 & 15 & \color{#f00}{11} \end{array}$

Also... $$x = i\cdot m + j = 2\cdot 6 + 5 = 17 $$

$$3^{17} \equiv 2 (\text{ mod } 29)$$

See Baby-step Giant-step