计算大数的模 [英] calculating modulo for large number

问题描述

全部

如何计算2 ^ 301 mod 77?我确实检查了链接 StackOverflow .但是不了解625 mod 221 = 183 mod 221的步骤.转换是如何发生的?

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?

推荐答案

看看问题基本上是(X * Y) % Z == ((X % Z) * (Y % Z)) % Z.

因此，2^301 % 77 == ((2^150 % 77) * (2^151 % 77)) % 77是起点.继续分裂，直到你有合理的数字，然后重新组合.在整个过程中，您都可以将号码保持在合理的大小.

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.

这篇关于计算大数的模的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！