What are the specifics and the possible outputs of Pollard's Rho algorithm?

Question

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
    end
    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
        y = ((y*y)%n + c)%n
        g = (x-y).gcd n
    end
    return g
end

number = gets.chomp.to_i
puts rho(number)

Answer 1

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.

Answer 2

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.