对于无符号长A和B,有没有办法(A*B)mod M没有溢出？

Question

我不想在Windows上安装GMP的噩梦.

我有两个数字A和B,unsigned long longs,最多数量级为10 ^ 10左右,但即使这样做((A%M)*(B%M))%M,我也会得到整数溢出.

是否有自制函数来计算(A*B)%M更大的数字？

Answer 1

如果模量M足够小ULLONG_MAX(如果它在10 ^ 10的范围内就是这种情况),你可以通过将其中一个因子分成两部分来分三步完成.我认为A < M和B < M和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;

对于较大的值,您可以将因子分成三个部分,但如果模数变得非常接近,ULLONG_MAX则变得难看.