Pollard Rho在不太大的投入上崩溃

Question

我实现了在wikipedia上给出的Pollard Rho算法

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

大输入会出错：

GNU MP：无法分配内存（size = 4294950944）

这是我的实施

mpz_class factor(mpz_class num)
{
    mpz_class x(2), y(2), d(1);
    while(d == 1)
    {
        x = polynomial(x);
        y = polynomial(polynomial(y));
        mpz_class diff = x - y;
        if(diff < 0)
        {
            diff *= -1;
        }
        mpz_gcd(d.get_mpz_t(), diff.get_mpz_t(), num.get_mpz_t());
    }
    if(d == num)
    {
        return -1;//failure
    }
    else
    {
        return d;//found factor
    }
}

mpz_class polynomial (mpz_class x)
{
    return ((x * x) + 1);
}

它适用于像121这样的输入，但在5540987上崩溃。我做错了什么？有没有一种方法可以改进，所以可以考虑这些数字？我见过some implementations似乎使用多项式((x*x)%N+c)%N（注意额外的mod n）。这是否有效，因为可以使用任何多项式？

Answer 1

有两个模运算有一个冗余，但其中一个正确修复了这个数字大小爆炸的问题，除非算法很早就终止了（它为121做了）。

这是否有效，因为可以使用任何多项式？

它有点微妙，将模数运算投入混合并不是“任何多项式”的情况。关键是算法所寻找的是x[i]和x[j]的一些序列中的两个值，使得i != j是abs(x[i] - x[j])的倍数（其中p并且N = pq和p都不是1），或者换句话说，q或abs(x[i] - x[j]) mod p = 0。在那个点上，当查看模x[i] ≡ x[j] mod p时，在序列中发现了一个循环，重要的是，如果p然后它们的差异是x[i] != x[j]的非零倍数，这给了一个机会从p提取一个因子..至少如果他们的差异不是也是N的倍数（在这种情况下，GCD的结果将是N本身并且没有因素出来）。

所以纯粹看数学模型N步骤在理论上是不必要的，循环模N没有这样的“帮助”。但是有可能，p所以如果我们减少模数N = pq，那么它的模数N不受干扰，算法仍然有效。更重要的是，减少模p实际上是非常重要的，因为它阻止了所涉及的数字变得不切实际的大，否则不仅会减慢算法的速度，而且最终会在实际（有限大小）硬件上失败。

这是很多理论上的理由，实现起来非常简单，

N