Como funciona o algoritmo rho de Pollard?

Question

Estou tentando entender como Pollard's rho algoritmo realmente funciona, mas eu simplesmente não consigo entender isso.Já li sua seção no livro CLRS e também na internet mas ainda não consigo entender sua estrutura ou análise.Esta é uma implementação java do pseudocódigo do livro CLRS junto com euclid gcd algoritmo:

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;
}

• Por que escolhe $x = (x_0^2 - 1) mod n$?
• O que $y$ realmente representa e por que foi escolhido para ser igual a $\{x_1,x_2,x_4,x_8,x_{16},...\}$?
• Por que isso computa $ ext{GCD}(y-x,n)$ e como é que $d$ acaba sendo um fator $n$?
• E por que o tempo de execução esperado é $O(n^{1/4})$ operações aritméticas e $O(2^{\beta/4} \beta^2)$ operações de bits assumindo que $n$ é $\beta$ pedaços de comprimento?

Eu entendo que se existe uma raiz quadrada não trivial de $x^2 ​​\equiv 1 \pmod{n}$ então $n$ é um composto e $x$ é um fator, mas $y-x$ não é uma raiz quadrada de $n$ é isso?

Answer 1

A ideia por trás de Pollard $ ho$ é que se você assumir qualquer função $f:[0, n - 1] \para [0, n - 1]$, a iteração $x_{k + 1} =f(x_k)$ deve cair em um ciclo eventualmente.Pegue agora $f$ como um polinômio, e considere-o módulo $n = p_1 p_2 \dotsm p_r$, onde o $p_i$ são primos:

$ begin {equação*} x_ {k + 1} = f (x_k) bmod n = f (x_k) bmod p_1 p_2 Dotsm p_r end {equação*} $

Assim, ele repete a mesma estrutura de iteração módulo cada um dos primos nos quais $n$ fatores.

Não sabemos nada sobre os ciclos, mas é fácil perceber que se você seguir $x_0=x'_0$ e:

$ Begin {align*} x_ {k + 1} & = f (x_k) x '_ {k + 1} & = f (f (x'_k)) end {align*} $

(ou seja, $x'$ avança duas vezes mais rápido) eventualmente $x'_k$ e $x_k$ irá abranger um (ou mais) ciclos (veja Algoritmo de detecção de ciclo do Floyd para detalhes), portanto, no nosso caso, $x'_k \equiv x_k \mod{p_i}$, e $\gcd(x'_k, x_k)$ será um fator $n$, espero que não seja trivial.

Qualquer polinômio funciona, mas queremos os irredutíveis (sem fatores não triviais, detectá-los não é o objetivo do exercício).Polinômios lineares não fornecem fatores, o próximo mais simples de calcular é quadrático, mas apenas $x^2$ também não funciona (redutível), então pegue $x^2 ​​+ 1$ Pela simplicidade.Lembre-se que a ideia aqui é trabalhar com números muito grandes, poucas e simples operações aritméticas são um bônus distinto.A análise do algoritmo (por ex.nos modelos "Algoritmos seminuméricos" de Knuth $f(x) \bmodp$ como uma função aleatória, que é próxima o suficiente para explicar as características gerais do algoritmo.