modulo - 如何计算大指数的模数？

Question

例如我想计算(相当有效)

2^1000003 模 12321

最后我想做 (2^1000003 - 3) mod 12321。有什么可行的方法吗？

Answer 1

基本模属性告诉我们

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 次迭代，只要记住 2^1000003 = 2 * 2^1000002 和 2^1000002 = (2⁵⁰⁰⁰⁰¹)² 等等...