Which factoring algorithm is more efficient?

Colleges & Universities Massachusetts Institute of Technology
1

<p>Does anyone happen to know which of the following two algorithms is more efficient with respect to time (when programmed and executed on a computer):</p>

<p>Pollard’s Rho Method
Pollard’s p-1 Method</p>

<p>Thanks.</p>

<p>EDIT: The algorithm will be used to factor large numbers…</p>

<p>47386483629775753
and
1834729514979351371768185745442640443774091</p>

2

<p>Have you referred to Knuth’s The Art of Computer Programming? I’d expect there to be an answer there.</p>

3

<p>Hah. There is actually another person in the world besides me who cares about factoring algorithms. Here’s a rundown on those two.</p>

<p>Pollard Rho is exceptionally fast at splitting numbers with small factors. Because it only uses modular multiplication and addition, it can do a lot of work in little time.</p>

<p>Pollard p-1 works only if p-1 (p being a factor of n) has small prime factors. It is almost independent of the size of n, as long as p-1 has small prime factors. It uses modular exponentiation, mostly, which is a time-consuming operation compared to + and x.</p>

<p>Both of these algorithms will take an excessively long time if the numbers are semiprimes (products of two primes of equal size). If you know they’re semiprimes, I’d use the quadratic sieve instead. It’s significantly more complicated than Pollard Rho or p-1, but it will work faster. If you know nothing about the factors of these numbers, I’d recommend you try trial division first.</p>

4

<p>pollard’s rho method. most definately.</p>

5

<p>What language? If you are using an arbitrary precision math library, you might want to check for primality functions and etc, as they are a lot more optimized for these huge numbers you want to process.</p>

6

<p>Thanks for the responses. I did some extensive research into Rho and understand how it works. However, it isn’t powerful enough for the second number. </p>

<p>I needed to either code an algorithm or write an essay for my math class…I wasn’t able to debug my code in time, so I just did an essay on Rho. I attempted it in both Java and Python. With Java, I had to use the BigInteger class; unfortunately, I could not find a direct way to obtain the square root of a BigInteger n…meaning, my factoring method ran n times as opposed to just n/2. As you can see, my program ran for a looong time. </p>

<p>Ah well, it’s over. Thanks again.</p>