1
$\begingroup$

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) 

2 Answers 2

2

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.

1

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.

  • 0
    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$.2012-04-03