计算a ^ n的模数比o(n)快

Question

我需要计算(a^n) mod b.我使用了这个java代码但是当n它太大时它不够快.

for (long i = 0; i < n; i++) {
    ans = (ans * a) % b;
}

正如您在上面的代码中看到的,n是一个long数字,所以这个算法不够快.你建议更快的算法吗？看起来这个问题似乎有点不同:快速计算n的方法!mod m其中m是素数？

Answer 1

利用模运算的特性

(x × y) modulo b == ((x modulo b) × (y modulo b)) modulo b

通过使用上面的乘法规则

(a^n) modulo b
= (a × a × a × a ... × a) modulo b 
= ((a modulo b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b

通过分而治之的方法计算结果.递归关系将是:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

这是C++实现:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}

时间复杂性是O(logn).

这是我原来的答案.希望能帮助到你!