# Integer factorization using Pollard Rho

I one of the programming contest, I was asked to list all the factors of a given number. As usual, I checked for divisibility till $\sqrt n$. However, my solution timed out for a number in the order of $10^{10}$.

I was then recommended to learn about Pollard Rho. I have sort of got the essence of this algorithm by reading this article.

It seems Pollard Rho algorithm can only be used to get just 2 factors and that too is sort of random.

So, how could I use Pollard Rho to obtain all the factors of the given integer? Or is there another elegant algorithm which will help me get all the factors in less than $\sqrt n$?

• Hint; You need to find one factor, then ... Commented May 20, 2017 at 8:46
• Probably, this question has multiple testcases? Factoring a number up to $10^{10}$ shouldn't time out too easily. How many testcases are there per run? Commented May 20, 2017 at 10:26
• If you feel like deterministic algorithm is better, learn about Lehman factorization. However, Pollard's Rho will outperform Lehman for large long long integers since Lehman is deterministic $O(n^{1/3})$ and Pollard's Rho is heuristic $O(n^{1/4})$. Commented May 20, 2017 at 11:31

Given a number $n$ and a prime factor $p$ of that number, i.e $p|n$, the other factors of $n$ are also factors of $\frac{n}{p}$, so if you have an algorithm for finding a prime factor of a number, you can just continue by applying that to $\frac{n}{p}$. If your algorithm gives you a factor $m$ that might not be prime (and I don't remember if Pollard Rho does), you'll of course also have to factor that.