2
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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