Is there a way to do (A*B) mod M without overflow for unsigned long long A and B?

Question

I don't want the nightmare of installing GMP on Windows.

I have two numbers A and B, unsigned long longs, on the order of magnitude 10^10 or so at most, but even when doing ((A%M)*(B%M))%M, I get integer overflow.

Are there homebrew functions for calculating (A*B)%M for larger numbers?

Answer 1

If the modulus M is sufficiently smaller than ULLONG_MAX (which is the case if it's in the region of 10^10), you can do it in three steps by splitting one of the factors in two parts. I assume that A < M and B < M, and M < 2^42.

// split A into to parts
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1);
unsigned long long temp = (a1 * B) % M;   // doesn't overflow under the assumptions
temp = (temp << 21) % M;                  // this neither
temp += (a2*B) % M;                       // nor this
return temp % M;

For larger values, you can split the factor in three parts, but if the modulus becomes really close to ULLONG_MAX it becomes ugly.