<s>[INST] Shank's Baby-Step Giant-Step for $3^x \equiv 2 \pmod{29}$ 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?
 [/INST] $$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
</s>