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?
Asked
Active
Viewed 2,581 times
0
-
I did not understand why express 625 as 183 + 2*221 ?? – name_masked Oct 25 '10 at 20:35
-
If I write it like `625 / 221 = 2, remainder 183`, do you understand? http://en.wikipedia.org/wiki/Remainder – Alin Purcaru Oct 26 '10 at 08:28
-
By the way. Don't you do these kind of stuff in school in the US? – Alin Purcaru Oct 26 '10 at 08:32
-
Erm... OK. I actually don't care. I was just a bit surprised that someone involved in IT doesn't understand the concept of _modulo_. – Alin Purcaru Oct 05 '12 at 19:47
-
1OK ..I don't really care either what you think. My question specifically states modulo for large numbers, not the concept. It might surprise you, but not many software engineers implement this on daily basis. – name_masked Oct 05 '12 at 19:58
2 Answers
3
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.
-
Sorry I didn't think of this before, but if you are using Java there's `BigInteger.modPow()`. Then you don't even need to implement it yourself, (unless this was a homework assignment?). – Jonathan Oct 29 '10 at 12:51
0
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
usr-local-ΕΨΗΕΛΩΝ
- 26,101
- 30
- 154
- 305