有沒有辦法做（A * B）mod M沒有溢出的無符號long long A和B？

Question

我不想在Windows上安裝GMP的噩夢。

我有兩個數字A和B，unsigned long long s，數量級最多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變得難看。