Algoritmo rho di Pollard: differenze tra le versioni

Versione delle 21:51, 12 ago 2016

Versione attuale delle 17:20, 21 nov 2022

(7 versioni intermedie di 6 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.

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]]