cperformancerecursionexponentiationmodular

Explanation of this recursive function of Fast_Modular_Exponentiation


Here is a code form a udemy course that I am currently taking. This piece of code is a recursive solution to solve (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;
}

In this, I didn't understand this line of code: (1LL * a * a) % MOD. I understand that in case n is even, (x^n)%MOD = ((x^(n/2))^2)%MOD, but i didn't get why we are calculating (a^2)%MOD, while we should be calculating ((a^2)^(1/2))%MOD. So, can someone explain me how this recursion step is correct and how recursion, in this case, is actually working?


Solution

  • Here when n is even then used

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

    which is also true and in code use this.

    Because algorithm says (a ⋅ b) mod m = [(a mod m) ⋅ (b mod m)] mod m

    Find details here with exaplaination