Algoritmo rho di Pollard: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Etichette: Ripristino manuale Modifica visuale |
|||
Riga 13:
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)
| |||