¿Cómo rho de Pollard algoritmo de trabajo?

Question

Estoy tratando de entender cómo funciona Pollard's rho algoritmo funcione, pero no puedo envolver mi cabeza alrededor de ella.Ya he leído su artículo en el CLRS libro y también en internet, pero todavía no puede entender su estructura o análisis.Esta es una implementación java de la pseudocódigo de la CLRS libro junto con 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 qué elegir $x = (x_0^2 - 1) \mod n$?
• ¿ $y$ en realidad representan y por qué es elegida para ser igual a $\{x_1,x_2,x_4,x_8,x_{16},...\}$?
• ¿Por qué calcular $ ext{MCD}(y-x,n)$ y ¿cómo $d$ resulta ser un factor de $n$?
• Y por qué se espera que el tiempo de ejecución es $O(n^{1/4})$ las operaciones aritméticas y $O(2^{\beta/4} \beta^2)$ bits operaciones suponiendo que $n$ es $\beta$ bits de largo?

Entiendo que si no existe no trivial de la raíz cuadrada de $x^2 \equiv 1 \pmod{n}$ entonces $n$ es un compuesto y $x$ es un factor, pero $y$x no es una raíz cuadrada de $n$ es?

Answer 1

La idea detrás de Pollard $ ho$ es que si usted toma cualquier función $f :[0, n - 1] \a [0, n - 1]$, la iteración $x_{k + 1} = f(x_k)$ debe caer en un ciclo de tiempo.A partir de ahora $f$ como un polinomio, y consideramos que es el modulo $n = p_1 p_2 \dotsm p_r$, donde el $p_i$ son los números primos:

$\begin{ecuación*} x_{k + 1} = f(x_k) \bmod n = f(x_k) \bmod p_1 p_2 \dotsm p_r \end{ecuación*}$

Por lo tanto, se repite la misma iteración de la estructura del modulo de cada uno de los números primos en la que $n$ factores.

No sabemos nada acerca de los ciclos, pero es fácil ver que si vas con $x_0 = x'_0$ y:

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

(es decir, $x'$ avances el doble de rápido) finalmente $x'_k$ y $x_k$ tendrá una duración de uno (o más) de los ciclos (ver Floyd ciclo del algoritmo de detección de para más detalles), en nuestro caso, $x'_k \equiv x_k \mod{p_i}$, y $\gcd(x'_k, x_k)$ va a ser un factor de $n$, esperemos un no-trivial.

Cualquier polinomio funciona, pero queremos irreductible queridos (no-trivial factores, la detección de esos no es el punto del ejercicio).Lineal de los polinomios de no dar factores, la próxima más simple para calcular es una ecuación cuadrática uno, pero sólo $x^2$ no funciona bien (reducible), así que $x^2 + 1$ para la simplicidad.Recuerde que la idea es trabajar con números muy grandes, pocas y simples operaciones aritméticas son una distinta bono.El análisis del algoritmo (por ejemplo,en Knuth del "Seminumerical algoritmos") modelos de $f(x) \bmod p$ como una función aleatoria, que es lo suficientemente cerca como para explicar las características generales del algoritmo.