Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?
I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?
Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?
Best Answer
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p \nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p \nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $p\equiv 5 \pmod{6}$ satisfies this condition. This follows the algorithm fails to factor primes $p \equiv 5 \pmod{6}$ out of $n$.