C++ 中大 mod 的模幂运算失败

Question

这是我用来计算 (n^p)%mod 的代码。不幸的是，当我从 main() 方法调用它时，它会因 mod 的大值（在我的例子中是 mod = 10000000000ULL）而失败。任何的想法;为什么？

ull powMod(ull n, ull p, ull mod) {
    ull ans = 1;
    n = n%mod;
    while(p) {
        if(p%2 == 1) {
            ans = (ans*n)%mod;
        }
        n = (n*n)%mod;
        p /= 2;
    }
    return ans;
}

这里，ull 是 unsigned long long 的类型定义。

Answer 1

这里可能出现的问题之一似乎是当您执行 (a*b)%c 时，a*b 部分本身可能会溢出，从而导致错误的答案。解决这个问题的一种方法是使用

的身份

(a*b)%c

等同于

(a%c * b%c)%c

这也将防止中间乘法溢出。

Answer 2

看来是躲不掉了

如果mod是10000000000ULL，在你程序的(a*b)%c中，a和b都小于mod，所以我们将它们视为9999999999ULL，a*b将是99999999980000000001，但unsigned long long只能表示2^64-1=18446744073709551615 < 99999999980000000001，因此您的方法将溢出。

Answer 3

你的代码行

 n = (n*n)%mod;

重复执行。只要 n 小于 mod，这就可能导致在某个时间点计算 (mod-1)*(mod-1)。

输入的 n 可能没有那么大，但是上面提到的代码行在循环中增加了 n。

Answer 4

是的，您可以在 C++ 中完成。正如其他人指出的那样，您不能直接这样做。使用一点点数论就可以将问题分解为两个可管理的子问题。

首先考虑10^10 = 2^10 * 5^10。这两个因数互质，因此您可以使用 Chinese remainder theorem 使用幂模 2^10 和模 5^10.

求幂模 10^10

请注意，在下面的代码中，magic 值 u2 和 u5 是使用 Extended Euclidean Algorithm. You don't need to program this algorithm yourself because these values are constants. I use maxima and its gcdex 函数计算的。

这是修改后的版本：

typedef unsigned long long ull;

ull const M  = 10000000000ull;

ull pow_mod10_10(ull n, ull p) {
  ull const m2 = 1024;    // 2^10
  ull const m5 = 9765625; // 5^10
  ull const M2 = 9765625; // 5^10 = M / m2
  ull const M5 = 1024;    // 2^10 = M / m5
  ull const u2 = 841;     // u2*M2 = 1 mod m2
  ull const u5 = 1745224; // u5*M5 = 1 mod m5

  ull b2 = 1;
  ull b5 = 1;
  ull n2 = n % m2;
  ull n5 = n % m5;

  while(p) {
    if(p%2 == 1) {
      b2 = (b2*n2)%m2;
      b5 = (b5*n5)%m5;
    }
    n2 = (n2*n2)%m2;
    n5 = (n5*n5)%m5;
    p /= 2;
  }

  ull np = (((b2*u2)%M)*M2)%M;
  np    += (((b5*u5)%M)*M5)%M;
  np    %= M;
  return np;
}

C++ 中大 mod 的模幂运算失败

Modular exponentiation fails for large mod in C++

c++

algorithm

cryptography

exponentiation

modular-arithmetic