java - Pollard rho 整数分解

Question

我正在尝试在 C/C++ 中实现 Pollard Rho 整数分解。Google 为我提供了问题的 Java 实现 here .

我不太了解 Java，所以我想出了什么 this .我在 C++ 中的实现适用于大多数情况，但在少数情况下却不行，比如我在那里使用的“9999”。

我知道 C++ 没有 Biginteger 类，所以我无法拥有它在 JAVA 中提供的全部功能，但我想分解足以满足 unsigned long long

请指出我的实现有什么问题。

Answer 1

问题就在这里:

#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 值.