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

Question

例如我想计算（合理有效）

2^1000003 模 12321

最后我想做 (2^1000003 - 3) mod 12321。有没有可行的方法来做到这一点？

Answer 1

基本的模数性质告诉我们

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

2) a * b (mod n) is (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 ⁵⁰⁰⁰⁰¹ ) ²等等......

Answer 2

在一些合理的 C 或 java 类语言中：

def modPow(Long base, Long exponent, Long modulus) = {
  if (exponent < 0) {complain or throw or whatever}
  else if (exponent == 0) {
    return 1;
  } else if (exponent & 1 == 1) { // odd exponent
    return (base * modPow(base, exponent - 1, modulus)) % modulus;
  } else {
    Long halfexp = modPow(base, exponent / 2, modulus);
    return (halfexp * halfexp) % modulus;
  }
}

这要求它modulus足够小，(modulus - 1) * (modulus - 1)并且base * (modulus - 1)不会溢出您正在使用的任何整数类型。如果modulus太大了，那么还有一些其他的技术可以弥补一点，但使用一些任意精度的整数算术库可能更容易攻击它。

然后，你想要的是：

(modPow(2, 1000003, 12321) + (12321 - 3)) % 12321

Answer 3

那么在Java中有一个简单的方法来做到这一点：

Math.pow(2, 1000003) % 12321;

对于没有Math.*内置函数的语言，它会有点困难。你能澄清一下这应该是哪种语言吗？