How to efficiently verify whether pow(a, b) % b == a in C (without overflow)

Question

I'd like to verify whether

pow(a, b) % b == a

is true in C, with 2 ≤ b ≤ 32768 (2¹⁵) and 2 ≤ a ≤ b with a and b being integers.

However, directly computing pow(a, b) % b with b being a large number, this will quickly cause C to overflow. What would be a trick/efficient way of verifying whether this condition holds?

This question is based on finding a witness for Fermat's little theorem, which states that if this condition is false, b is not prime.

Also, I am also limited in the time it may take, it can't be too slow (near or over 2 seconds). The biggest Carmichael number, a number b that's not prime but also doesn't satisfy pow(a, b)% b == a with 2 <= a <= b (with b <= 32768) is 29341. Thus the method for checking pow(a, b) % b == a with 2 <= a <= 29341 shouldn't be too slow.

Answer 1

You can use the Exponentiation by squaring method.

The idea is the following:

• Decompose b in binary form and decompose the product
• Notice that we always use %b which is below 32768, so the result will always fit in a 32 bit number.

So the C code is:

/*
 * this function computes (num ** pow) % mod
 */
int pow_mod(int num, int pow, int mod)
{
    int res = 1

    while (pow>0)
    {
        if (pow & 1)
        {
            res = (res*num) % mod;
        }
        pow /= 2;
        num = (num*num)%mod;
    }

    return res;
}