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。我理解万一(x^n)%MOD = ((x^(n/2))^2)%MOD，是偶数的话，但是我不明白为什么我们要计算(a^2)%MOD，，而我们应该计算((a^2)^(1/2))%MOD。那么，有人能解释一下这个递归步骤是如何正确的吗?在这种情况下，递归是如何工作的呢？

Answer 1

这里，当n甚至被使用时

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

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

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

查找包含投诉的详细信息这里

Answer 2

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

算法的全部解释可以在这里找到：指数化，见右向左二进制方法。