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\\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}}}$ iterazioni; 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))}$ (perché se n non è primo allora ha almeno un fattore primo ${\displaystyle p\leq n^{\frac {1}{2}}}$).

Pseudocodice

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

Bibliografia

• Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994. ISBN 88-08-09154-6