calculating modulo for large number

Question

All,

How can I calculate 2^301 mod 77? I did check out the link StackOverflow. But did not understand the step wherein 625 mod 221 = 183 mod 221. How did the conversion take place?

Answer 1

Take a look at the question here for an answer to your question.

Basically, (X * Y) % Z == ((X % Z) * (Y % Z)) % Z.

So, as a starting point, 2^301 % 77 == ((2^150 % 77) * (2^151 % 77)) % 77. Keep splitting until you have reasonable numbers, then recombine. You will be able to keep your numbers at a reasonable size the whole way through.

Answer 2

Hello, I don't understand the second part of your post, probably because you didn't include the link you actually followed. But your problem can be solved reading this page and implementing a proper algorithm of modular exponentiation