将一个数字提高到一个巨大的指数

Question

我得到了数字 3 和一个变量 'n'，它可以高达 1 000 000 000（十亿）。我必须打印 3^n modulo 100003 的答案。我尝试了以下方法：

我尝试使用函数 std::pow(3,n)，但它不适用于大指数（无法在此过程中应用模数）。
我尝试实现我自己的函数，将数字 3 的 n 次方计算出来，这样我就可以在需要时应用模数，但是当用非常大的数字进行测试时，这个方法被证明太慢了。
最后我尝试对数字 'n' 进行质因数分解，然后使用 'n' 的因数（以及它们出现的次数）来构建答案，这似乎就像我能想到的最好的方法（如果它是正确的）。问题是对于一个已经是质数的巨大数字我该怎么办？

所以这些就是我的想法，如果有人认为有更好的方法（或者如果我的方法之一是最佳的），我将不胜感激任何指导。

Answer 1

利用属性模运算

(a × b) modulo M == ((a module M) × (b modulo M)) modulo M

通过使用上面的乘法规则

(a^n) modulo M 
= (a × a × a × a ... × a) modulo M 
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M

分而治之计算结果。递归关系将是：

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);
}

Answer 2

这是为了补充 Kaidul 的回答。

100003 是一个素数，它立即投射在 Fermat's Little Theorem 中：任何数的素数次方都与自身同余，以该素数为模。这意味着您不需要加注到 n 次方。一个n % 100002的力量就够了。

编辑：示例。

比如说，n是200008，也就是100002 * 2 + 6。现在，

3 ^ 200007 =
3 ^ (100002 + 100002 + 6) = 
3 ^ 100002 * 3 ^ 100002 * 3 ^ 6

FLT 声称 (3 ^ 100002) % 100003 == 1，上面的最后一行，模 100003，减少到 3 ^ 6。一般来说，对于素数 p,

(k ^ n) % p == k ^ (n % p)

当然，如果指数n大于p，它只会加快计算速度。根据您的要求（指数 100，模 100003），没有什么可以减少的。直奔凯杜尔进场

将一个数字提高到一个巨大的指数

Raising a number to a huge exponent

c++

arrays

algorithm

math

integer-arithmetic