Visualizza wikitesto di 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 [[Numeri pseudo-casuali|pseudo-casuale]] di numeri [[aritmetica modulare|modulo]] ''n'' (che è il numero che si cerca di fattorizzare): una sequenza ampiamente usata è
:<math>\begin{cases}x_0=2\\ x_{i+1}=x_i^2+1\mod n\end{cases}</math>
dove ''x<sub>k</sub>'' è il ''k''-esimo numero della sequenza.
Se la successione è "sufficientemente casuale", allora si dovrebbe osservare un ciclo dopo circa <math>\sqrt{n\pi/2}</math> iterazioni; se però ''p'' è un fattore di ''n'', allora la sequenza si ripeterà anche modulo ''p'', ma dopo circa <math>\sqrt{p\pi/2}</math> 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<sub>i</sub>''-''x<sub>j</sub>'', 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<sub>2i</sub>''-''x<sub>i</sub>'', 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]], <math>O(p^{1/2}\ln^2(n))</math> dove ''p'' è il fattore di ''n''; volendolo esprimere in funzione di quest'ultimo, è <math>O(n^{1/4}\ln^2(n))</math> (perché se ''n'' non è primo allora ha almeno un fattore primo <math>p \leq n^{\frac{1}{2}}</math>).

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

== Bibliografia ==
*Harold Davenport, ''Aritmetica superiore'', Bologna, Zanichelli, 1994. ISBN 88-08-09154-6

{{portale|matematica}}

[[Categoria:Algoritmi per la matematica|Rho di Pollard]]
[[Categoria:Teoria dei numeri]]