例如我想计算(相当有效)
2^1000003 模 12321
最后我想做 (2^1000003 - 3) mod 12321。有什么可行的方法吗?
最佳答案
基本模属性告诉我们
1) a + b (mod n)
是 (a (mod n)) + (b (mod n)) (mod n)
,所以你可以分两步操作
2) a * b (mod n)
是 (a (mod n)) * (b (mod n)) (mod n)
,所以你可以使用模幂(伪代码):
x = 1
for (10000003 times) {
x = (x * 2) % 12321; # x will never grow beyond 12320
}
当然,您不应该进行 10000003 次迭代,只要记住 21000003 = 2 * 21000002 和 21000002 = (2500001)2 等等...
关于modulo - 如何计算大指数的模数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20410389/