Как работает алгоритм rho Полларда?

Question

Я пытаюсь понять, как это Pollard's rho алгоритм на самом деле работает, но я просто не могу обмозговать это.Я уже прочитал его раздел в книге CLRS, а также в Интернете, но все еще не могу понять его структуру или анализ.Это java-реализация псевдокода из книги CLRS вместе с 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},...\}$?
• Почему это вычисляет $\текст{GCD}(y-x,n)$ и как это происходит $d$ оказывается, это фактор $n$?
• И почему ожидаемое время выполнения составляет $O(n^{1/4})$ арифметические операции и $O(2^{\бета/4} \бета^2)$ битовые операции , предполагающие , что $n$ является $\ бета-версия$ кусочки длинные?

Я понимаю, что если существует нетривиальный квадратный корень из $x ^2 \equiv 1 \pmod{n}$ тогда $n$ является составным и $x$ является фактором, но $y - x$ не является квадратным корнем из $n$ так ли это?

Answer 1

Идея , лежащая в основе Полларда $\ро$ это если вы возьмете какую-либо функцию $f :[0, n - 1] \к [0, n - 1]$, итерация $x_{k + 1} = f(x_k)$ в конце концов, они должны попасть в замкнутый круг.Возьми сейчас $f$ как многочлен, и рассматривайте его по модулю $n = p_1 p_2 \dotsm p_r$, где $p_i$ являются простыми числами:

$\begin{уравнение*} x_{k + 1} = f(x_k) \bmod n = f(x_k) \bmod p_1 p_2 \dotsm p_r \конец {уравнение*}$

Таким образом, он повторяет одну и ту же итерационную структуру по модулю каждого из простых чисел, в которые $n$ факторы.

Мы ничего не знаем о циклах, но легко увидеть, что если вы идете с $x_0 = x'_0$ и:

$\begin{выровнять*} x_{k + 1} &= f(x_k) \\ x'_{k + 1} &= f(f(x'_k)) \конец{выровнять*}$

(т.е., $x'$ продвигается в два раза быстрее) в конечном итоге $x_k$ и $x_k$ будет охватывать один (или несколько) циклов (см. Алгоритм определения цикла Флойда для деталей), таким образом, в нашем случае, $x_k \эквивалент x_k \mod{p_i}$, и $\gcd(x'kk, x_k)$ будет фактором $n$, надеюсь, нетривиальный.

Любой многочлен работает, но нам нужны неприводимые (никаких нетривиальных факторов, их обнаружение не является целью упражнения).Линейные многочлены не дают множителей, следующим по простоте вычисления является квадратичный, но просто $x^2$ тоже не работает (сводимо), поэтому возьмите $x^2 + 1$ для простоты.Помните, что идея здесь заключается в том, чтобы работать с очень большими числами, небольшое количество и простые арифметические операции являются отличным бонусом.Анализ алгоритма (например,в "Получисловых алгоритмах" Кнута) модели $f(x) \bmod p$ как случайная функция, которая достаточно близка, чтобы объяснить общие характеристики алгоритма.