User:Bengl/Rho factoring

This is pretty easy.

Every description i've found online for this is horrible, they make it sound sooooo complicated but really it's very easy.

Here is the simplified rho factoring algorithm.

Input: a number $n$ to be factored, a polynomial $f(x)$, and a starting number $x_{0}=y_{0}$ Output: a factor (or two) of $n$

The squence of $x_{i}$'s is such that $x_{i}=f(x_{i-1})$ mod $n$ and the sequence of $y_{i}$'s is such that $y_{i}=f(f(y_{i-1}))$ mod $n$. Calculate these as you need them. For each $x_{i}$ and $y_{i}$ pair, if $|y-x|$ divides $n$, then HOLY CRAP you've got a factor. If not, then try $gcd(|y-x|,n)$. If there actually is one of those other than 1, then, being a greatest common divisor, it's clearly a factor (divisor) of $n$. Otherwise, move on to the next pair of $x_{i}$ and $y_{i}$.

That's all.

Try it a few times and youll see that this is really simple.