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.
Best Answer
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}$$