algorithm - Pollard Rho是否对某些数字无效？

我试图基于我在维基百科上发现的伪代码实现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

唯一的区别是：我不返回失败，而是尝试不同的初始化变量，因为wikipedia还指出：
这里x和y对应于x i{\displaystylex{i}x{i}和x j
{\displaystyle x{j}x{j}核心思想部分。请注意
这个算法可能找不到一个重要的因素，即使n是
混合成的。在这种情况下，可以使用
起始值不是2或不同的g（x）{\displaystyle
g（x）}g（x）。
波拉德罗对某些数字不起作用吗他们有什么特点还是我做错了什么？

最佳答案

波拉德罗对偶数不起作用。如果您有一个偶数，在应用Pollard Rho查找奇数因子之前，首先删除所有因子2。
pollard rho正确地将因子25设为5，但它同时找到两个因子5，因此它返回因子25。没错，但没用所以Pollard Rho找不到任何幂的因子（正方形、立方体等）。
虽然我没有运行它，但是你的Pollard Rho函数看起来没问题维基百科关于改变起点的建议可能有效，但通常无效。正如维基百科也建议的那样，最好是改变随机函数g。最简单的方法是增加加数；而不是x 2+1，使用x 2+c，其中c最初是1，每次失败后增加到2，3。

关于algorithm - Pollard Rho是否对某些数字无效？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48196783/