最小非負殘渣：大數

-3

我試圖建立一個C++程序，可以解決所述模塊化一致性：最小非負殘渣：大數

Ñ^ P = X（模q）的，

其中n是一個很小的數字，p和q是非常大的任意素數。我試過多次這樣做，但我總是遇到內存溢出問題。任何幫助表示讚賞。

來源

2013-06-11 Trancot

你能顯示你的源代碼嗎？ – suspectus

也許吧。我可以檢查它是否仍然可以辨認。這將需要一秒，但因爲我在Mac上並行運行Windows Server。 – Trancot

我說「可譯」，因爲代碼存儲的地方只是衆多無關代碼塊中的一個，它們全部註釋掉了。這是因爲它只是一個測試.cpp文件，所以我在一個.cpp文件中有一堆註釋掉的程序。那有意義嗎？ – Trancot

有一個簡單的算法b^ë（MOD米）：

function powerMod(b, e, m) 
    x := 1 
    while e > 0 
     if e % 2 == 1 
      x := (b * x) % m 
     b := (b * b) % m 
     e := e // 2 # integer division 
    return x

你應該不計算b^Ë，然後執行模運算，因爲中間數字會很大。我會把它留給你來翻譯成你的首選語言，用數據類型來存儲你需要的大數字。我在my blog討論這個算法。

來源

2013-06-11 23:04:00 user448810

謝謝@ user448810。這將是有用的。 – Trancot

'e：= e // 2＃整數除法'是什麼意思？ – Trancot

unsigned long long powerMod（unsigned long long b，unsigned long long e，unsigned long long m） \t int x = 1; \t而（E> 0） \t { \t \t如果（E％2 == 1） \t \t { \t \t \t X =（B * X）％M; \t \t} \t \t b =（b * b）％m; \t \t e = e – Trancot

看看你對你的問題的評論，這聽起來像你試圖將非常大的值推入變量，無法保存大的值。

看看這裏的有關數據類型和範圍的詳細信息，他們可以容納：
http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.110).aspx

我發現與非負數最大的數據類型範圍爲unsigned long long。它具有從0到18,446,744,073,709,551,615的值範圍。

來源

2013-06-11 22:34:31 Doug

這個數字和我的系統一樣嗎？ – Trancot

這是無符號64位整數的最大值。（0xffffffffffffffff）等於18,446,744,073,709,551,615。這些值在Visual Studio 2012上是真實的。所以要回答你的問題，你將無法使用像你想要的大數字，而不需要像Peter Wood在評論中提到的大數字庫那樣的庫的幫助部分到您的問題帖子。如果使用它可以解決您的問題，請確保加註他的評論。 – Doug

您是否看到Peter Wood的評論？ – Trancot

最小非負殘渣：大數

回答

相關問題