Algoritmo rho di Pollard: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Algoritmo: typo fix |
→Algoritmo: aggiunta spiegazione della complessità computazionale |
||
Riga 11:
È 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 ===
| |||