calculating modulo for large number
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?
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.
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
链接地址: http://www.djcxy.com/p/58280.html下一篇: 计算大数模