How to avoid overflow in fast modular exponentiation

Question

I am trying to solve a question on SPOJ which requires modular exponentiation. I am using the following C code

long long modpow(long long a,long long b,long long mod)
{
    long long product,pseq;
    product=1
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=(product*pseq)%mod;
        pseq=(pseq*pseq)%mod;
        b>>=1
    }
    return product;
}

The problem is when I want to calculate (2^249999999997)%999999999989, it gives answer 0 because of overflow. How can I avoid overflow?

Answer 1

Untestet, but you get the idea. This should work as long as 2*mod is less than the maximum representable long long value and a, b, and mod are positive.

long long modpow(long long a,long long b,long long mod)
{
    long long product,pseq;
    product=1;
    pseq=a%mod;
    while(b>0)
    {
        if(b&1)
            product=modmult(product,pseq,mod);
        pseq=modmult(pseq,pseq,mod);
        b>>=1;
    }
    return product;
}

long long modmult(long long a,long long b,long long mod)
{
    if (a == 0 || b < mod / a)
        return (a*b)%mod;
    long long sum;
    sum = 0;
    while(b>0)
    {
        if(b&1)
            sum = (sum + a) % mod;
        a = (2*a) % mod;
        b>>=1;
    }
    return sum;
}

Answer 2

One additional suggestion is to make use of the fact that 999999999989 is a prime. By using the relation, (a^n) = a % n (where n is a prime), u can simplify the operation.

Answer 3

You can use unsigned long long instead of long long, it will help you to play with higher values, whose range is 0 to 18,446,744,073,709,551,615.