modular-arithmetic - 计算 2^n Mod m 的最快方法，其中 n 和 m 是随机整数

Question

当 2^n 除以 m 其中 n 和 m 是随机整数时，如果有任何可能的有效方法可以找到余数，我一直在徘徊。是否有任何方程式可以将 n 和 m 分给我以得到余数，还是我们必须遵循递归方法？请注意，我是初学者，而且我才刚刚开始，所以可能无法理解太复杂的东西。

提前致谢。

Answer 1

fkdosilovic 的回答是正确的，但不是最快的。

他的算法在 O(n) 时间内运行，但有可能达到 O(log(n))。

由于所有数字 2^n 都可以表示为集合 {2^1, 2^2, 2^4, 2^8 ..., 2^floor(lg(n))} 的乘积，我们只需要计算这些值并将它们相乘。例如 2^13 = 2^1 * 2^4 * 2^8。这是一个python代码。

def fast_powmod(n, m):
    pow2 = 2
    result = 1
    while n > 0:
        if n % 2 == 1:
            result = (result * pow2) % m
        pow2 = (pow2 * pow2) % m
        n >>= 1

    return result

Answer 2

乘法的模运算是这样工作的：

(a * b) % x = ( (a % x) * (b % x) ) % x

这是 C++ 代码：

#include <cstdio>
#include <cstdlib>

using namespace std;

int powmod(int n, int m) {
  int ret = 1;
  for(int i = 0; i < n; ++i)
    ret = ( (ret % m) * (2 % m) ) % m; // expression from above
  return ret; // returns 2 to the power n modulo m
}

int main() {

  int n, m; scanf("%d%d", &n, &m);
  printf("%d\n", powmod(n, m));

  return 0;
}

Answer 3

此 javascript 代码正确处理非常大的 n 值。

function fastMod(n, m){
var pow2 = 2
var result = 1
while(n > 0){
    if(n&1){
        result = (result * pow2) % m 
    }
   n/=2
    pow2 = (pow2 * pow2) % m   
}
console.log(result)
}
fastMod(77, 100)

Answer 4

在m是素数的情况下，费马小定理可以帮助您：

如果p是素数，那么对于任何整数a，该数a^p − a都是 的整数倍p。

例如，如果a = 2and p = 7, 2^7 = 128, and128 − 2 = 7 × 18是 的整数倍7。