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

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)

-

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.

-

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.

-
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