algorithm - 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

唯一的区别:我不返回失败，而是尝试不同的初始化变量，正如维基百科也指出的那样:

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 不适用于偶数。如果您有一个偶数，请先删除所有 2 的因数，然后再应用 Pollard Rho 求出奇数因数。

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

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