java - Pollard rho 整数因式分解

Question

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

我不太了解 Java，所以我想出了这个。我在 C++ 中的实现适用于大多数情况，但在少数情况下，我使用的不是“9999”。

我知道 C++ 没有 Biginteger 类，所以我不能拥有它在 JAVA 中提供的全部功能，但我想分解 15 位数字，这足以unsigned long long

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

Answer 1

问题就在这里：

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

您的abs宏中缺少一些括号。尝试：

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

反而。abs(x-xx)（考虑在 case 中展开时会发生什么x-xx <= 0。）

另外，为什么你的 gcd 函数返回一个 int 而不是 BigInteger？

您还应该知道（假设 unsigned long long 是 64 位整数类型）此代码对于N大于2**32：如果x（或xx）大于或等于2**32thenx*x将包装模数2**64，给您错误的值为x*x % N.

Answer 2

我发现了一个区别：Java 代码分配c和x是new BigInteger(N.bitLength(), random)，而 C++ 代码使用rand() % N，这是一个较小的随机范围。对于值 9999，二进制是 10011100001111，因此 Java 代码将给出c最大值x16383。