3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Ecir Hana Apr 3 at 21:08
  • $\begingroup$ 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? $\endgroup$ – Ecir Hana Apr 3 at 21:15
  • $\begingroup$ @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 ? $\endgroup$ – Peter Apr 4 at 6:09
  • $\begingroup$ 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. $\endgroup$ – Ecir Hana Apr 4 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.