Algoritmo rho di Pollard

L'algoritmo rho di Pollard è un algoritmo di fattorizzazione di numeri interi, basato sull'aritmetica modulare. Ideato da John Pollard nel 1975, è adatto in particolare alla ricerca di fattori piccoli; è stato usato nel 1981 per fattorizzare l'ottavo numero di Fermat. È un algoritmo probabilistico, nel senso che non garantisce di produrre un risultato.

Algoritmo

L'algoritmo si basa sulla generazione di una sequenza pseudo-casuale di numeri modulo n (che è il numero che si cerca di fattorizzare): una sequenza ampiamente usata è

${\displaystyle {\begin{cases}x_{0}=2\\f(x_{i+1})=x_{i}^{2}+1\mod n\end{cases}}}$ 

dove x_k è il k-esimo numero della sequenza. Se la successione è "sufficientemente casuale", allora si dovrebbe osservare un ciclo dopo circa ${\displaystyle {\sqrt {n\pi /2}}}$  iterazione; se però p è un fattore di n, allora la sequenza si ripeterà anche modulo p, ma dopo circa ${\displaystyle {\sqrt {p\pi /2}}}$  passi.

Poiché tuttavia p non è conosciuto, bisogna ricorrere ad un altro metodo per verificare le eventuali ripetizioni, e cioè calcolare il massimo comun divisore tra n e la differenza x_i-x_j, per ogni coppia (i,j). Nella pratica, tuttavia, calcolare il massimo comun divisore per ogni coppia di indici renderebbe il test molto lento, quasi quanto il metodo delle divisioni per tentativi: si può dimostrare però che è sufficiente considerare le differenze x_2i-x_i, velocizzando notevolmente l'esecuzione dell'algoritmo.

È possibile tuttavia che il massimo comun divisore sia n: in tal caso l'algoritmo ha fallito, ed è necessario riprovare con un'altra sequenza, oppure con un diverso punto di partenza. Se n' è primo, il metodo fallisce per ogni successione e ogni punto di partenza.

La complessità computazionale dell'algoritmo è, nella notazione O-grande, ${\displaystyle O(p^{1/2}\ln ^{2}(n))}$  dove p è il fattore di n; volendolo esprimere in funzione di quest'ultimo, è ${\displaystyle O(n^{1/4}\ln ^{2}(n))}$ 

Pseudocodice

1. x=2, y=2, d=1;
2. Se d=1
   1. x=f(x);
   2. y=f(f(x));
   3. d=MCD(x,y);
3. Se d=n l'algoritmo fallisce; altrimenti d divide n

Implementazione| PARI-GP

/*

• P-1 Factorization (Pollard)
• N numero da fattorizzare
• B numero della base dei fattori (i primi B primi)
• s=1 è opzionale ed indica il numero di base a scelta casuale
• /

M_P(n,B,s=1)= local(m, a, p, j, d, g, l, i, lgn, status=1);{
    if(n <= 1 | !bittest(n,0) | s<= 0, error("Input non valido"); return); 
    l= floor(lgn/log(2));
    for(i=1,s, 
       until(a, a=random()%n);    /* genero a finche' a non divide n */
       /* print("base scelta numero ", i, ": a = ",a); */
       g=gcd(a,n);  
       if(g > 1, print(g," e` un fattore di ",n); status=0; return(status););
       p = 3;
       j = 1;
       d = 1;
       lgn = log(n); 
       while(d == 1 && j <= B,  
               a = lift(Mod(a,n)^(p^floor(lgn/log(p))));
               d = gcd(a-1, n); 
               if(d > 1 && d < n , print(d," e` un fattore di ",n); status=0; return(status););
               j = j++;
               p = nextprime(p++);
            );
       m = 1;   
   	while(d == 1 && m <= l,
   	       a = lift(Mod(a,n)^2);

d = gcd(a-1,n); if(d > 1 && d < n, print(d," e` un fattore di ",n); status=0; return(status);); m = m++;

       );
    );	
    if(d == 1 | d == n, print("Prova ad incrementare B"));
    return(status);

}

Bibliografia

• Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994. ISBN 8808091546

Collegamenti esterni

• (EN) Spiegazione didattica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica