Объяснение этой рекурсивной функции 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

Здесь, когда даже 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 и вычтите 1 из n, чтобы получить четное n на следующем шаге.

Полное объяснение алгоритма можно найти здесь: https://en.m.wikipedia.org/wiki/Modular_exponentiation, см. Двоичный метод с написанием справа налево