math - 计算大数的模

Question

全部，

如何计算 2^301 mod 77？我确实查看了StackOverflow链接。但是不明白625 mod 221 = 183 mod 221的步骤。转换是如何发生的？

score 3 · Accepted Answer

看看这里的问题以回答您的问题。

基本上，(X * Y) % Z == ((X % Z) * (Y % Z)) % Z.

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

score 0 · Accepted Answer

我不明白您帖子的第二部分，可能是因为您没有包含您实际关注的链接。但是您的问题可以通过阅读此页面并实施适当的模幂运算来解决

2 回答 2