Why the function is failing in case of numbers greater than 48 digits?

Question

I am trying to find

(a^b) % mod

where b and mod is upto 10^9, while l can be really large i have tested upto 48 digits with success using this relation

(a^b) % mod = (a%mod)^b % mod

#define ll long long int
ll powerLL(ll x, ll n,ll MOD)
        {

        ll result = 1;
   

 while (n) {
        if (n & 1)
            result = result * x % MOD;
        n = n / 2;
        x = x * x % MOD;
    }
    return result;
}


ll powerStrings(string sa, string sb,ll MOD)
{


    ll a = 0, b = 0;


    for (size_t i = 0; i < sa.length(); i++)
        a = (a * 10 + (sa[i] - '0')) % MOD;

    for (size_t i = 0; i < sb.length(); i++)
        b = (b * 10 + (sb[i] - '0')) % (MOD - 1);

    return powerLL(a, b,MOD);
}

powerStrings("5109109785634228366587086207094636370893763284000","362323789",354252525) returns 208624800 but it should return 323419500. In this case a is 49 digits

powerStrings("300510498717329829809207642824818434714870652000","362323489",354255221) returns 282740484 , which is correct. In this case a is 48 digits

Is something wrong with the code or I will have to use other method of doing the same??

Answer 1

It does not work because it is not mathematically correct.

In general, we have that pow(a, n, m) = pow(a, n % λ(m), m) (with a coprime to m) where λ is the Carmichael function. As a special case, when m is a prime number, then λ(m) = m - 1. That situation is also covered by Fermat's little theorem. That's only a special case, it does not always work.

λ(354252525) = 2146980, if I hack that in then the right result comes out. (the base is not actually coprime to the modulus though)

In general you would need to compute the Carmichael function for the modulus, which is non-trivial, but feasible for small moduli.