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)