Algoritmo rho di Pollard: differenze tra le versioni

Versione delle 22:11, 16 apr 2013

Versione attuale delle 17:20, 21 nov 2022

(10 versioni intermedie di 8 utenti non mostrate)

Riga 3:

== 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\\ f(x_{i+1})=x_i^2+1\mod n\end{cases}</math>

dove ''x_k'' è 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> iterazioneiterazioni; 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_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]], <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 ===

Riga 17:

#While (''d''=1)

##''x''=''f''(''x'');

##''y''=''f''(f''(''x''y));''

##''d''=MCD(''|x-y|'',''n'');

#Se ''d''=''n'' l'algoritmo fallisce; altrimenti ''d'' divide ''n''

Riga 23:

== Bibliografia ==

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

== Collegamenti esterni ==

{{portale|matematica}}

[[Categoria:Algoritmi numericiper la matematica|Rho di Pollard]]

[[Categoria:Teoria dei numeri]]