代码之家 › 专栏 › 技术社区 › whacko__Cracko

Pollard Rho整数因子分解

factorization math c c++ java

whacko__Cracko · 技术社区 · 16 年前

我尝试在C/C++中实现Purrar Rho整数分解。谷歌给了我一个Java实现的问题。 here .

我不太懂Java,所以我想出了什么 this 我在C++中的实现适用于大多数情况,但不是像我所用的那种“9999”那样。

我知道C++没有BigType类,所以我不能拥有它在Java中给出的全部功能,但我想分解15个数字,这就足够了。 unsigned long long

请指出我的实现中的错误。

2 回复 | 直到 16 年前

Mark Dickinson Alexandru 16 年前

问题就在这里:

#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 将包装模块 2**64 ,为您提供错误的值 x*x % N .

Adrian Cox 16 年前

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