Pollard的rho算法是如何工作的？

Question

我试图了解如何 Pollard's rho 算法实际上工作，但我只是不能把我的头围绕它。我已经在CLRS书和互联网上阅读了它的部分，但仍然无法理解它的结构或分析。这是CLRS书中的伪代码的java实现，以及 euclid gcd 算法:

public static void pollardRho(int n) {
    Random rand = new Random();
    int i = 1;
    int x0 = rand.nextInt(n);
    int y = x0;
    int k = 2;
    while (true) {
        i++;
        int x = (x0 * x0 - 1) % n;
        int d = gcd(y - x, n);
        if (d != 1 && d != n) {
            System.out.println(d);
        }
        if (i == k) {
            y = x;
            k *= 2;
        }
        x0 = x;
    }
}

public static int gcd(int a, int b) {
    // fixes the issue with java modulo operator % returning negative 
    // results based on the fact that gcd(a, b) = gcd(|a|, |b|)
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int tmp = b;
        b = (a % b);
        a = tmp;
    }
    return a;
}

• 它为什么选择 $x=(x_0^2-1)\mod n$?
• 做什么？ $y$ 实际表示以及为什么选择等于 $\{x_1,x_2,x_4,x_8,x_{16},...\}$?
• 为什么它计算 $ ext{GCD}(y-x,n)$ 以及如何 $d$ 结果是...... $n$?
• 为什么预期的运行时间是 $O(n^{1/4})$ 算术运算和 $O(2^{\beta/4}\beta^2)$ 位操作假设 $n$ 是 $\beta$ 位长？

我明白，如果存在一个不平凡的平方根 $x^2\equiv1\pmod{n}$ 然后 $n$ 是一个复合和 $x$ 是一个因素，但 ＜y-x＞ 不是一个平方根 $n$ 是吗？

Answer 1

波拉德背后的想法 $ ho$ 如果你有什么功能 $f :[0,n-1]\到[0,n-1]$, ，迭代 $x_{k+1}=f(x_k)$ 最终必须陷入一个循环。现在就拿 $f$ 作为多项式，并认为它是模 $n=p_1p_2\dotsm p_r$, ，其中 $p_i$ 是素数:

$\开始{方程*} x_{k+1} =f(x_k)\bmod n =f(x_k)\bmod p_1p_2\dotsm p_r \end{方程*}$

因此，它重复相同的迭代结构模每个素数到其中 $n$ 因素。

我们对周期一无所知，但很容易看出，如果你和 $x_0=x'_0$ 和:

$\开始{对齐*} x_{k+1} &=f(x_k) \\ x'_{k+1} &=f(f(x'_k)) \结束{对齐*}$

（即, $x'$ 快两倍）。 $x'_k$ 和 $x_k$ 将跨越一个（或多个）周期（见 弗洛伊德的周期检测算法 有关详细信息），因此在我们的情况下, $x'_k\equiv x_k\mod{p_i}$, 和 $\gcd(x'_k,x_k)$ 将是一个因素 $n$, ，希望是一个不平凡的。

任何多项式都有效，但我们想要不可约的（没有非平凡的因素，检测那些不是练习的重点）。线性多项式不给出因子，下一个最简单的计算是二次，但只是 $x^2$ 也不起作用（可还原），所以采取 $x^2+1$ 为简单起见。记住这里的想法是处理非常大的数字，很少和简单的算术运算是一个明显的好处。算法的分析（例如在Knuth的"Seminumerical algorithms"）模型中 $f(x)\bmod p$ 作为随机函数，其足够接近以解释算法的整体特性。