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

user_2204668 0
Viewed 209

I'd like to verify whether

pow(a, b) % b == a

is true in C, with 2 ≤ b ≤ 32768 (215) 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.

modulus memory-efficient integer-overflow c
2 Answers

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;
}
user_12120120

You are doing modular arithmetic in Z/bZ.

Note that, in a quotient ring, the n-th power of the class of an element is the class of the n-th power of the element, so we have the following result:

(a^b) mod b = ((((a mod b) * a) mod b) * a) mod b [...] (b times)

So, you do not need a big integer library.

You can simply write a C program using the following algorithm (pseudo-code):

  • declare your variables a and b as integers.
  • use a temporary variable temp that is initialized with a.
  • do a loop with b steps, and compute (temp * a) mod b at each step, to get the new temp value.
  • compare the result with a.

With this formula, you can see that the highest value for temp is 32768, so you can choose an integer to store temp.

user_83349910
Related