Pollard-Rho Factorization Parallelization

Question

I recently stumbled upon a paper on a parallelization of Pollard's Rho algorithm, and given my specific application, in addition to the fact that I haven't attained the required level of math, I'm wondering if this particular parallelization method helps my specific case.

I'm trying to find two factors—semiprimes—of a very large number. My assumption, based on what little I can understand of the paper, is that this parallelization works well on a number with lots of smaller factors, rather than on two very large factors.

Is this true? Should I use this parallelization or use something else? Should I even use Pollard's Rho, or is there a better parallelization of a different factorization algorithm?

Answer 1

The wikipedia article states two concrete examples:

Number                Original code      Brent's modification
18446744073709551617  26 ms              5 ms
10023859281455311421  109 ms             31 ms

First of all, run these two with your program and take a look at your times. If they are similar to this ("hard" numbers calculating 4-6 times longer), ask yourself if you can live with that. Or even better, use other algorithms like simple classic "brute force" factorization and look at the times they give. I guess they might have a hard-easy factor closer to 1, but worse absolute times, so it's a simple trade-off.

Side note: Of course, parallelization is the way to go here, I guess you know that but I think it's important to emphasize. Also, it would help for the case that another approach lies between the Pollard-rho timings (e.g. Pollard-Rho 5-31 ms, different approach 15-17 ms) - in this case, consider running the 2 algorithms in seperate threads to do a "factorization race".

In case you don't have an actual implementation of the algorithm yet, here are Python implementations.

Answer 2

The basic idea in factoring large integers is to use a variety of methods, each with its own pluses and minuses. The usual plan is to start with trial division by primes to 1000 or 10000, followed by a few million Pollard rho steps; that ought to get you factors up to about twelve digits. At that point a few tests are in order: is the number a prime power or a perfect power (there are simple tests for those properties). If you still haven't factored the number, you know that it will be hard, so you will need heavy-duty tools. A useful next step is Pollard's p-1 method, followed by its close cousin the elliptic curve method. After a while, if that doesn't work, the only methods left are quadratic sieve or number field sieve, which are inherently parallel.

The parallel rho method that you asked about isn't widely used today. As you suggested, Pollard rho is better suited to finding small factors rather than large ones. For a semi-prime, it's better to spend parallel cycles on one of the sieves than on Pollard rho.

I recommend the factoring forum at mersenneforum.org for more information.