Algoritmo rho di Pollard: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Algoritmo: typo fix |
|||
Riga 9:
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
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>
| |||