Pollard Rho 不适用于某些数字吗？

Question

我正在尝试根据我在维基百科上找到的伪代码来实现 Pollard Rho，但它似乎不适用于数字 4、8 和 25，而且我不知道为什么。

这是我的代码：

    long long x = initXY;
    long long y = initXY;
    long long d = 1;

    while (d == 1) {
        x = polynomialModN(x, n);
        y = polynomialModN(polynomialModN(y, n), n);

        d = gcd(labs(x - y), n);
    }
    if (d == n)
        return getFactor(n, initXY + 1);

    return d;

这是我的多项式函数：

long long polynomialModN(long long x, long long n) {
    return (x * x + 1) % n;
}

这是来自维基百科的示例伪代码：

x ← 2; y ← 2; d ← 1
while d = 1:
    x ← g(x)
    y ← g(g(y))
    d ← gcd(|x - y|, n)
if d = n: 
    return failure
else:
    return d

唯一的区别：我没有 return 失败，而是尝试了不同的初始化变量，正如维基百科也指出的那样：

Here x and y corresponds to x i {\displaystyle x_{i}} x_{i} and x j {\displaystyle x_{j}} x_{j} in the section about core idea. Note that this algorithm may fail to find a nontrivial factor even when n is composite. In that case, the method can be tried again, using a starting value other than 2 or a different g ( x ) {\displaystyle g(x)} g(x).

Pollard-Rho 是否对某些数字不起作用？他们有什么特点？还是我做错了什么？

Answer 1

Pollard Rho 不适用于偶数。如果你有一个偶数，在应用 Pollard Rho 找到奇数因子之前，先删除所有 2 的因子。

Pollard Rho 正确地分解了 25，但它同时找到了 5 的两个因子，所以它 returns 是 25 的因子。这是正确的，但没有用。所以 Pollard Rho 不会找到任何幂（平方、立方等）的因数。

虽然我没有运行它，但你的 Pollard Rho 函数看起来没问题。维基百科关于改变起点的建议可能会奏效，但通常不会。正如维基百科还建议的那样，最好更改随机函数 g。最简单的方法是增加加数；而不是 x²+1，使用 x²+c，其中 c 最初是 1，每次失败后增加到 2、3、...。

Answer 2

这里，由于x可以和n-1一样大，所以你的polynomialModN函数中的乘积会溢出。

Pollard Rho 不适用于某些数字吗？

Does Pollard Rho not work for certain numbers?

algorithm

factorization