4
$\begingroup$

So I think I understand how to calculate something like $(208\cdot 2^{-1})\mod 421$ using extended euclidean algorithm. But how would you calculate something like $(208\cdot2^{-21})\mod 421$?

Thanks, this is basically for my cryptography class; I'm just trying to understand the "big step, baby step" algorithm.

$\endgroup$
  • $\begingroup$ You're solving for the inverse. What times 208*2^21 mod 421 is equal to 1? $\endgroup$ – Jonny Nov 10 '14 at 20:54
3
$\begingroup$

Remember that one of the rules of exponents is that $$(x^a)^b = x^{ab}.$$ So we can rewrite $$208 \cdot 2^{-21} \pmod{421}$$ as $$208 \cdot (2^{-1})^{21} \pmod{421}.$$ You can then solve for the modular multiplcative inverse by one of a few techniques, including, as you note, the Extended Euclidean Algorithm. With this specific example, we get $$x \equiv 208 \cdot (2^{-1})^{21} \pmod{421}$$ $$\equiv 208 \cdot (211)^{21} \pmod{421}$$ $$\equiv 208 \cdot 329 \pmod{421}$$ $$\equiv 230 \pmod{421}$$

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