Pollard rho整數因子

我想在C/C++中實現Pollard Rho整數因子分解，Google給了我一個問題here的Java實現。Pollard rho整數因子

我不知道Java那麼好，所以我想出了this。我在C++中的實現對大多數情況下都適用，但不是很少，就像我在那裏使用的那個「9999」一樣。

我知道C++沒有BIGINTEGER類，所以我不能擁有的全部功能，因爲它在JAVA給人但我想因式分解15位數字，這足以unsigned long long

請指出錯在哪在我的實施中。

來源

2010-02-21 whacko__Cracko

你有可能在問題中粘貼C代碼，以便它可以用於後代？（或者這是不恰當的？我是一個相對較新的人，可能是60行的粘貼。） – 2010-02-21 11:40:21

也有C++的大整數實現。最受歡迎的可能是GNU：http://gmplib.org/ – Manuel 2010-02-21 12:58:31

問題的最大值就在這裏：

#define abs(x) (x>0)?(x):(-x)

你錯過了一些括號中的abs宏。試試：

#define abs(x) ((x)>0 ? (x) : -(x))

改爲。（考慮當abs(x-xx)在x-xx <= 0的情況下展開時會發生什麼。）

另外，爲什麼你的gcd函數返回一個int而不是BigInteger？

還應該知道，（假設無符號長長是64位整數類型）這個代碼將不正確地爲N大於2**32工作：如果x（或xx）大於或等於2**32然後x*x將以模進行換行，給您x*x % N的錯誤值。

來源

2010-02-21 11:33:27

這就是爲什麼內聯函數儘可能優於宏。 – 2010-02-21 21:34:28

要明確一點，它不是缺少的括號，而是真正重要的減號旁邊的*錯位*括號。爲了安全地執行乘法，查找SqrMod和MultiplyMod。 – xan 2010-02-23 04:24:12

我已經發現一個區別：Java代碼分配c和x是new BigInteger(N.bitLength(), random)，而C++代碼使用rand() % N，這是一個更小的隨機範圍。對於值9999，二進制是10011100001111，因此Java代碼會給c和x的16383

來源

2010-02-21 11:21:52

當N大於32767時，rand（）的較小範圍可能會影響性能，但是您對N = 9999時會發生什麼的解釋沒有做到，對我來說沒有任何意義。 – 2010-02-21 13:33:08

我打了一個錯字：9999小數點是10011100001111，需要14位來表示。如果N = 9999，則BigInteger（N.bitLength（），random）將產生一個從0到2^14-1的整數，而rand（）％N將產生一個從0到9998的整數。它不是代碼中的關鍵錯誤，但它也不是Java版本的準確翻譯。 – 2010-02-21 13:53:04

Pollard rho整數因子

回答

相關問題