Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)
share|improve this question

2 Answers 2

up vote 1 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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.