User:Bengl/Rho factoring

From Wikipedia, the free encyclopedia

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₀ = y₀ 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.