Lecture 36: 04/27/2012

Pollard’s Rho Algorithm and Integer Factorization.

Suppose you’re given a number n = p*q where p and q are large primes. We’d like to factor n efficiently, say O(\sqrt(p)) where p <= q.

We bounced a couple ideas around like the grade school method of factoring a number, or even using the birthday problem. However, these don't give us a good enough running time.

At last we came to the idea of Floyd's cycle-finding algorithm and using it to factor our number n. We start with two pebbles, one slow the other fast, at x_0, and at each step we compute x_slow = f(x_slow) and x_fast = f(f(x_fast)). If we find that x_slow == x_fast, then we've found a cycle.

Supposing we know p ahead of time, we use a pseudo-random generator, e.g., f(x) = x^2 + 1 (mod p), to generate a sequence of integers. Pollard's algorithm is a modified Floyd's algorithm, we compute d = gcd(|x_slow – x_fast|, n). If d != 1, then we've found a non-trivial factor of n, unless of course x_slow == x_fast.

The time until x_slow == x_fast is the length of the transient segment, plus at most the length of the cycle. In total, this adds up to about \sqrt(p), so the algorithm terminates in the correct running time. If it returns an answer, it is correct, however, there is a non-zero probability that the algorithm will not return an answer at all.

There was one last topic we wanted to cover, although we didn't have time. What if you want to generate a random number AND know its factorization. There is a nice randomizing algorithm to generate some large n and its prime factorization. If you'd like to see it, let me know and I'll write up a nice post about it.

Also, Professor Blum will not be giving any more lectures next week, but we can still organize some lectures with students on Wednesday and Friday to see something new. If anyone is interested in learning about something, let me know and we'll make it happen.

Our last class will be on Monday, taught by Steven Rudich. Please remember to sign up for a final exam slot starting on Tuesday. I will make a separate post for the exam requirements.