Pollard's rho algorithm termination

331 Views Asked by At

Pollard's rho algorithm is a simple probabilistic method for factoring a composite number $N$. There are two parameters one can choose when starting the algorithm: the initial function values $x$ ($0 \le x \le N-1$) and the polynomial (most often just its constant term $b$, where $1 \le b \le N-3$).

Even if one tried all of the parameter values within given ranges, could it still happened that the algorithm would not be find any factors?

1

There are 1 best solutions below

4
On

The pollard-rho method eventually arrives in a loop, so it is possible that with given parameters , it never finds a factor. The method is called pollard-rho because the letter rho contains a straight line and a circle (in which the method will land unless it finds a factor)