Take the 2-minute tour ×

I'm trying to implement a simple prime factorization program (for Project Euler), and want to be able to use Pollard's Rho algorithm. I read the Wikipedia, wolfram|alpha, and planet math explanations of this algorithm. I think I understand the steps, but I don't fully understand the underlying math. How does this algorithm work? Also, I tried to do it by hand and was unable to get an answer for some numbers, such as 9. Why is that? Lastly, how do I pick the polynomial function to use? is f(x) = (x^2 + a) mod n all that is necessary?

Note: I'm a freshman in High School, and I've taken up to Pre-Calculus, so that's my level.

Edit: This is what I wrote in ruby; However, for a lot of numbers it just gives back that same number. (like entering 9 returns 9)

def rho(n)
    if n%2 == 0
        return 2
    x = Random.rand(2...(n-3))
    y = x
    c = y
    g = 1
    while g==1
        x = ((x*x)%n + c)%n
        y = ((y*y)%n + c)%n
        g = (x-y).gcd n
    return g

number = gets.chomp.to_i
puts rho(number)
share|improve this question

2 Answers 2

up vote 2 down vote accepted

Pollard's Rho algorithm is essentially a smart way to guess possible factors of a number - the $x$ values are generated with a kind of pseudo-random number generator, and by the construction, it is fairly likely to find a factor. There is no hard-and-fast guarantee here, since it essentially relies on a probabilistic argument, but it is proven empirically.

Your choice of $f$ is somewhat uncommon and may be related to the problem you are experiencing with finding only trivial factorizations. I have good experience with simply using $f(x) = (x^2 + 1) \mod n$, and retrying with $(x^2+2) \mod n$, $(x^2 + 3) \mod n$ etc. if this fails.

share|improve this answer

Take $n=9$, and say $x=4$. First time through the loop, $x=4^2+4=2$, $y=2^2+4=8$ (all computations reduced modulo 9), $\gcd(x-y,9)=3$, problem solved.

share|improve this answer
Why does it work with x = 4, y = 2 but not with x = 4, y = 3? –  Vishnu Apr 3 '12 at 1:20
Huh? Your program starts by setting $y$ equal to $x$, so the way you have set it up you don't get to say $x=4,y=2$. What do you mean? –  Gerry Myerson Apr 3 '12 at 1:44
Wait... What is your function (f)? –  Vishnu Apr 3 '12 at 1:59
I'm following the code you posted, insofar as I understand it. First you choose $x$ at random between 2 and $n-3=6$; I chose 4. Then you set $y$ equal to $x$, and $c$ equal to $y$, so $c=4$. Then you are iterating the function $f(t)=t^2+c$, so that's $t^2+4$. –  Gerry Myerson Apr 3 '12 at 3:41

Your Answer


