Fast_Modular_Exponentiation这个递归函数的解释

Question

这是我目前正在学习的 udemy 课程的代码。这段代码是递归求解(a^n)%b.

int fastExpo(int a, long long n, int MOD) {
    if(n == 0)
        return 1;

    /// (a^n) % MOD
    if(n % 2 == 0)
        /// a ^ n = ((a ^ 2) ^ (n/2))
        return fastExpo((1LL * a * a) % MOD, n / 2, MOD);

    /// a ^ n = a * (a ^ (n - 1))
    return (1LL * a * fastExpo(a, n - 1, MOD)) % MOD;
}

在此，我没看懂这行代码：(1LL * a * a) % MOD。我知道如果 n 是偶数，(x^n)%MOD = ((x^(n/2))^2)%MOD，但我不明白为什么我们要计算 (a^2)%MOD，而我们应该计算 ((a^2)^(1/2))%MOD。那么，有人可以向我解释一下这个递归步骤是如何正确的，以及递归在这种情况下实际上是如何工作的吗？

Answer 1

((a^2)^(1/2))%MOD 等于 a%MOD。因此，如果 n 是奇数算法，则将当前值乘以 a，然后从 n 中减去 1，以便在下一步中得到偶数 n。

可以在此处找到算法的完整说明：https://en.m.wikipedia.org/wiki/Modular_exponentiation，请参阅从右到左的二进制方法

Answer 2

这里当n为偶数时使用

(x^n)%MOD = (((x^2)%MOD)^(n/2))%MOD

这也是正确的，在代码中使用它。

因为算法说 (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

查找详细信息here 并进行解释

Fast_Modular_Exponentiation这个递归函数的解释

Explanation of this recursive function of Fast_Modular_Exponentiation

c

recursion

performance

modular

exponentiation