大數乘法的模數

是的我知道這個問題可能看起來很天真，但我在谷歌和本網站上搜索了很多，但無法找到令人滿意的答案。我只是想計算（A * B）％MOD，如果a長且b和MOD也是如此。假設MOD比A和B都大，使得A％MOD = A和B％MOD = B，但A * B大於64位。如何計算（A * B）％MOD的正確值？大數乘法的模數

來源

2014-01-09 unrealsoul007

Matt：我不同意dup。無法解析：A * B =（A-X）* B + X * B，您總是可以將A分解爲更小的數字。例如。設置X =樓層（A/2）。如果子結果仍然過大，則可以應用相同的過程。 –

這是接受答案的人的評論「如果long的最大值是2^63 - 1，那麼只要x <290331368171」，1768431 * x就不會溢出。但是這正是我懷疑如果A * B溢出的情況。 – unrealsoul007

換句話說，分成等等 –

這裏的基本思想是首先定義一個非溢出函數，它在其算術中利用負數。然後根據它還使用位操作來定義timesmod。時間複雜度爲O(N)，其中N是使用的位數（在這種情況下爲64）。

#include <iostream> 
using namespace std; 

typedef long long BigInt; // must be signed, to detect overflow 

BigInt A = 0x7fffffffffffff01; 
BigInt B = 0x7fffffffffffff02; 
BigInt M = 0x7fffffffffffff03; 

// For simplicity it is assumed x, y, and m are all positive. 
BigInt addmod(BigInt x, BigInt y, BigInt m) 
{ 
    x %= m; 
    y %= m; 
    BigInt sum = x-m+y; // -m <= sum < m-1 
    return sum < 0 ? sum + m : sum; 
} 

BigInt timesmod(BigInt x, BigInt y, BigInt m) 
{ 
    x %= m; 
    y %= m; 
    BigInt a = x < y ? x : y; // min 
    BigInt b = x < y ? y : x; // max 
    BigInt product = 0; 
    for (; a != 0; a >>= 1, b = addmod(b,b,m)) 
    if (a&1) product = addmod(product,b,m); 
    return product; 
} 

int main() 
{ 
    cout << "A = " << A << endl; 
    cout << "B = " << B << endl; 
    cout << "M = " << M << endl; 
    cout << "A*B mod M = " << timesmod(A,B,M) << endl; 
    return 0; 
}

輸出：

A = 9223372036854775553 
B = 9223372036854775554 
M = 9223372036854775555 
A*B mod M = 2

這是很容易確認因爲A=-2和B=-1 MOD M。

注意：此代碼未優化。

來源

2014-01-09 22:16:10 Matt

問題是您正在使用'BigInt'的簽名類型，因此您無法可靠地檢測到溢出（它會導致未定義的行爲）。您需要使用無符號類型來獲得可靠的溢出行爲。 –

@ChrisDodd你是絕對正確的;感謝您指出了這一點。我更新了'addMod'函數來解決這個問題。 – Matt

您的方法與我寫的最後一個方法幾乎相同： 'long long int multiply（long long a，long long b，long long mod） { \t long long result; \t if（b == 0）return 0LL; \t \t result = multiply（a，b >> 1，mod）; \t結果=（結果+結果）％mod; （b＆1）result =（result + a）％mod; \t \t返回結果; }' – unrealsoul007

我現在沒有時間回答這個問題，所以我會給一個指針，稍後再回過頭來編輯這個答案。在你喜歡的算法教科書（或搜索引擎）中查找「Schrage乘法」。基本思想是將A和B分成幾塊，分別處理這些部分，然後合併這些部分以完成計算。

來源

2014-01-09 21:12:44 user448810

我認爲你可以形成兩個部分（高64位和低64位）的128位產品，並減少每個模p。假設p大約是4^k，那麼您可以大致計算出hi64/(p>>k)之間的數字p。這應該會給你k-1位的正確答案。從整體上減去很多p，現在hi64的位數減少了大約k-1。再次這樣做，但計算(hi64 << k-1)/(p >> k)。然後再做一次，計算(hi64 << k+k-2)/(p >> k)。

施拉格的技巧，由另一張海報建議，聽起來像一個更好的交易，但我不明白。希望那張海報能夠回覆並完成他的回答！

來源

2014-01-10 00:27:42 tmyklebu

大數乘法的模數

回答

相關問題