我正在尝试在 C/C++ 中实现 Pollard Rho 整数分解。Google 为我提供了问题的 Java 实现 here .
我不太了解 Java，所以我想出了什么 this .我在 C++ 中的实现适用于大多数情况，但在少数情况下却不行，比如我在那里使用的“9999”。
我知道 C++ 没有 Biginteger 类，所以我无法拥有它在 JAVA 中提供的全部功能，但我想分解足以满足 unsigned long long
请指出我的实现有什么问题。
最佳答案
问题就在这里:
#define abs(x) (x>0)?(x):(-x)
您的 abs 中缺少一些括号宏。尝试:
#define abs(x) ((x)>0 ? (x) : -(x))
相反。 (考虑在 abs(x-xx) 的情况下扩展 x-xx <= 0 会发生什么。)
此外，为什么您的 gcd 函数返回一个 int 而不是 BigInteger？
您还应注意(假设 unsigned long long 是 64 位整数类型)此代码对于 N 将无法正常工作。大于 2**32 : 如果 x (或 xx )大于或等于 2**32然后 x*x将换模 2**64 , 为您提供错误的 x*x % N 值.
关于java - Pollard rho 整数分解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2305652/