# Pollard's rho algorithm termination

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 Answer

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)

• For example, let's say that for $N=10, x=1, b=2$ it arrives in the loop, ok. If I try with different $x$ and $b$ it will possibly break out of the loop. My question is, for given $N$, could it happen that every combination of $0 \le x \le N-1$ and $1 \le b \le N-3$ will always end up in a loop? Conversely, is it always possible to break out of the loop by choosing different parameters $x$ and $b$? – Ecir Hana Apr 3 at 21:08
• What I try to ask is that a loop is detected by $GCD > 1$ but it could also mean $GCD = N$, in which case one could try with different parameters. Will this "restarting" eventually always lead to a factor? – Ecir Hana Apr 3 at 21:15
• @EcirHana Do you mean choosing an arbitary other polynomial or a concrete strategy like replacig $x^2+1$ by $x^2+2,x^2+3,x^2+4$ and so on ? – Peter Apr 4 at 6:09
• I was thinking the later, i.e. $x^2+b$. But it's a good question and I assume that there might be some arbitrary polynomial for with it factors but I don't see a systematic way of finding it. Trying $1 \le b \e N-3$ seems much easier. – Ecir Hana Apr 4 at 8:08