如何计算大指数的mod? [英] How to calculate the mod of large exponents?

问题描述

例如，我想计算(合理有效)

For example I want to calculate (reasonably efficiently)

2 ^ 1000003 mod 12321

2^1000003 mod 12321

最后我想做(2 ^ 1000003-3)mod12321.有什么可行的方法吗?

And finally I want to do (2^1000003 - 3) mod 12321. Is there any feasible way to do this?

推荐答案

基本模属性告诉我们

1)a + b (mod n)是(a (mod n)) + (b (mod n)) (mod n)，因此您可以将操作分为两个步骤

1) a + b (mod n) is (a (mod n)) + (b (mod n)) (mod n), so you can split the operation in two steps

2)a * b (mod n)是(a (mod n)) * (b (mod n)) (mod n)，因此您可以使用模幂(伪代码):

2) a * b (mod n) is (a (mod n)) * (b (mod n)) (mod n), so you can use modulo exponentiation (pseudocode):

x = 1
for (10000003 times) {
    x = (x * 2) % 12321; # x will never grow beyond 12320
}

当然，您不应该进行10000003迭代，只需记住2 ^1000003 = 2 * 2 ^1000002 和2 ^1000002 = (2 ⁵⁰⁰⁰⁰¹ ) ² 等等...

Of course, you shouldn't do 10000003 iterations, just remember that 2^1000003 = 2 * 2^1000002 , and 2^1000002 = (2⁵⁰⁰⁰⁰¹)² and so on...

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