Come funziona l'algoritmo Rho Pollard?

Question

Sto cercando di capire come funzionano in realtà l'algoritmo Pollard's rho, ma non riesco a avvolgermi la testa. Ho già letto la sua sezione nel libro del CLRS e anche su Internet ma non riesce ancora a capire la sua struttura o analisi. Questa è un'implementazione Java della pseudocodice dal libro CLRS insieme all'algoritmo 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;
}

.

.
• Perché scegliere $ x= (x_0 ^ 2 - 1) \ mod n $ ?
• Cosa fa $ y $ In realtà rappresenta e perché è scelto di essere uguale a $ \ {x_1, x_2, x_4, x_8, x_ {16}, ... \} $ ?
• Perché calcola $ \ text {gcd} (yx, n) $ e come fa $ d $ < / SPAN> risulta essere un fattore di $ N $ ?
• E perché il tempo di esecuzione previsto è $ o (n ^ {1/4}) $ operazioni aritmetiche e $ O (2 ^ {\ beta / 4} \ beta ^ 2) $ Operazioni di bit Supponendo che $ n $ è $ \ beta $ bit long?

Capisco che se esiste una radice quadrata non banali di $ x ^ 2 \ equiv 1 \ pmod {n} $ allora $ N $ è un composito e $ x $ è un fattore, ma $ y - X $ non è una radice quadrata di $ n $ è?

Answer 1

L'idea alla base del pollard $ \ rho $ Se prendi qualsiasi funzione $ f: [0, n - 1] \ a [0, n - 1] $ , l'iterazione $ x_ {k + 1}= f (x_k) $ deve cadere in a ciclare alla fine. Prendi ora $ f $ come polinomiale e consideralo modulo $ n= p_1 p_2 \ dotsm p_r $ , dove la $ p_i $ sono numeri primi:

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

Così ripete la stessa struttura di iterazione modulo ciascuno dei primi in cui $ N $ fattori.

Non sappiamo nulla dei cicli, ma è facile vedere che se vai con $ x_0= x'_0 $

e: $ \ Begin {Align *} x_ {k + 1} &= f (x_k) \\ x '_ {k + 1} &= f (f (x'_k)) \ end {allinea *} $

(cioè, $ x '$ anticipi due volte più veloce) alla fine $ x'_k $ e $ x_k $ spanterà un (o più) cicli (vedere Algoritmo di rilevamento del ciclo di Floyd per i dettagli), quindi nel nostro caso, $ x'_k \ equiv x_k \ mod {p_i} $ , e $ \ gcd (x'_k, x_k) $ sarà un fattore di $ N $ , si spera un non banale.

Qualsiasi lavoro polinomiale, ma vogliamo quelli irriducibili (senza fattori non banale, rilevando quelli non è il punto dell'esercizio). I polinomi lineari non danno fattori, il prossimo più semplice da calcolare è un quadratico, ma solo $ x ^ 2 $ non funziona né (riducibile), quindi prendere < Span Class="Math-Container"> $ x ^ 2 + 1 $ per semplicità. Ricorda l'idea qui è lavorare con numeri molto grandi, poche e semplici operazioni aritmetiche sono un bonus distinto. L'analisi dell'algoritmo (ad esempio in modelli "algoritmi seminumerici" di Knuth) $ f (x) \ bmod p $ come funzione casuale, che è abbastanza vicino per spiegare il Caratteristiche complessive dell'algoritmo.