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

Question

I do not need a nightmare to install GMP on Windows.

I have two numbers A and B, unsigned long long s, in magnitude 10 ^ 10 or so, but even when ((A%M)*(B%M))%M executed, I get an integer overflow.

Are there homegrown functions to compute (A*B)%M for large numbers?

Answer 1

If the module M sufficiently smaller than ULLONG_MAX (which takes place if it is in the region of 10 ^ 10), you can do this in three steps by dividing one of the factors into 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 divide the coefficient into three parts, but if the module becomes really close to ULLONG_MAX , it becomes ugly.