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

Question

上给出的 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: Cannot allocate memory (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).

Does this work because any polynomial could be used?

这有点微妙，将模运算混入其中并不是 "any polynomial" 的情况。关键是算法寻找的是某些序列中的两个值 x[i] 和 x[j] 以及 i != j 这样 abs(x[i] - x[j]) 是 p 的倍数（其中N = pq 而 p 和 q 都不是 1)，或者换句话说，abs(x[i] - x[j]) mod p = 0 或 x[i] ≡ x[j] mod p。那时，当以 p 为模查看时，在序列中发现了一个循环，重要的是，如果 x[i] != x[j] 则它们的差是 p 的非零倍数，这提供了一个机会提取 a来自 N 的因子 .. 至少如果它们的差异不是 N 的倍数（在这种情况下，GCD 的结果将是 N 本身并且没有因子出来）。

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

说了这么多理论上的道理，实现起来真的很简单，

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

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

Pollard Rho crashes on inputs that are not too big

c++

algorithm

math

gmp