Metodo Rho di Pollard

[GreenLink]

Scrivo perchè non ho ben chiaro questo metodo per la fattorizzazione degli interi.
Non capisco come mai si cerchi di generare una successione di iterati tramite una funzione: è unicamente per scegliere un campione casuale all'interno di $ZZ_n$?
E poi quando vado a calcolare i vari $mcd(x_i-x_j,n)$ chi mi assicura che non siano sempre $1$?

[Lord K]

"GreenLink":Non capisco come mai si cerchi di generare una successione di iterati tramite una funzione: è unicamente per scegliere un campione casuale all'interno di $ZZ_n$?

Reputo di sì, il punto è che si cerca di confrontare due numeri presi "a caso" proprio per ottenerne particolari proprietà.

E poi quando vado a calcolare i vari $mcd(x_i-x_j,n)$ chi mi assicura che non siano sempre $1$?

Il principio si basa sul fatto che avendo $n$ ci interessa trovare $p$ primo tale che sia il più piccolo primo che divide $n$ ed allora se $EE x,y \in ZZ_n$ tali che $x != y$ e $x\equiv y (n)$ [La parentesi sta per $modn$] allora discende che $p<= GCD(x-y,n)<=n$

Osserva che se fosse sempre $mcd(x_i-x_j,n)=1$ allora per l'idea precedente $n$ sarebbe identicamente uguale a $1$.