What is the fastest factorization algorithm?

Question

I've written a program that attempts to find Amicable Pairs. This requires finding the sums of the proper divisors of numbers.

Here is my current sumOfDivisors() method:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

So I need to do lots of factorization and that is starting to become the real bottleneck in my application. I typed a huge number into MAPLE and it factored it insanely fast.

What is one of the faster factorization algorithms?

Answer 1

General Number Field Sieve

Answer 2

This is a paper of the Integer Factorization in Maple.

"Starting from some very simple instructions—“make integer factorization faster in Maple” — we have implemented the Quadratic Sieve factoring algorithm in a combination of Maple and C..."

http://www.cecm.sfu.ca/~pborwein/MITACS/papers/percival.pdf

Answer 3

Depends how big your numbers are. If you're searching for amicable pairs you're doing a lot of factorisations, so the key may not be to factor as quickly as possible, but to share as much work as possible between different calls. To speed up trial division you could look at memoization, and/or precalculating primes up to the square root of the biggest number you care about. It's quicker to get the prime factorisation, then calculate the sum of all factors from that, than it is to loop all the way up to sqrt(n) for every number.

If you're looking for really big amicable pairs, say bigger than 2^64, then on a small number of machines you can't do it by factorising every single number no matter how fast your factorisation is. The short-cuts which you're using to find candidates might help you factor them.

Answer 4

Shor's Algorithm: http://en.wikipedia.org/wiki/Shor%27s_algorithm

Of course you need a quantum computer though :D

Answer 5

I would suggest starting from the same algorithm used in Maple, the Quadratic Sieve.

1. Choose your odd number n to factorize,
2. Choose a natural number k,
3. Search all p <= k so that k^2 is not congruent to (n mod p) to obtain a factor base B = p1, p2, ..., pt,
4. Starting from r > floor(n) search at least t+1 values so that y^2 = r^2 - n all have just factors in B,
5. For every y1, y2, ..., y(t+1) just calculated you generate a vector v(yi) = (e1, e2, ..., et) where ei is calculated by reducing over modulo 2 the exponent pi in yi,
6. Use Gaussian Elimination to find some of the vectors that added together give a null vector
7. Set x as the product of ri related to yi found in the previous step and set y as p1^a * p2^b * p3^c * .. * pt^z where exponents are the half of the exponents found in the factorization of yi
8. Calculate d = mcd(x-y, n), if 1 < d < n then d is a non-trivial factor of n, otherwise start from step 2 choosing a bigger k.

The problem about these algorithms is that they really imply a lot of theory in numerical calculus..

Answer 6

The question in the title (and the last line) seems to have little to do with the actual body of the question. If you're trying to find amicable pairs, or computing the sum of divisors for many numbers, then separately factorising each number (even with the fastest possible algorithm) is absolutely an inefficient way to do it.

The sum-of-divisors function, σ(n) = (sum of divisors of n), is a multiplicative function: for relatively prime m and n, we have σ(mn) = σ(m)σ(n), so

σ(p₁^k₁…p_r^k_r) = [(p₁^k₁+1-1)/(p₁-1)]…[(p_r^k_r+1-1)/(p_r-1)].

So you would use any simple sieve (e.g. an augmented version of the Sieve of Eratosthenes) to find the primes up to n, and, in the process, the factorisation of all numbers up to n. (For example, as you do your sieve, store the smallest prime factor of each n. Then you can later factorize any number n by iterating.) This would be faster (overall) than using any separate factorization algorithm several times.

BTW: several known lists of amicable pairs already exist (see e.g. here and the links at MathWorld) – so are you trying to extend the record, or doing it just for fun?

Answer 7

Before trying the quadratic sieve method that others have suggested, you should also check out the Pollard rho method (and Brent's variants of it). It's very simple to code up, and it'll allow factorization of numbers up to 10**25 or so in reasonable time. Beyond that, you'll need to get out the big guns, like the Multiple Polynomial Quadratic Sieve and the Elliptic Curve Method. Of these two, the MPQS method is probably easier to code, and slightly faster; ECM has the advantage that its running time depends mainly on the size of the smallest prime factor, rather than on the size of the number you're trying to factor, so it's a good method for finding smallish factors (e.g. 20 digits or so) of huge numbers. For your needs, it's probably not all that useful. The Number Field Sieve mentioned in the first answer above is asymptotically the fastest known factorization method, but its extra speed doesn't really kick in until you're looking at numbers with more than 100 digits.

So a good general strategy involves multiple methods:

1. Use trial division (up to 10**6 or so), to pull out any small factors.
2. Then use Pollard Rho to find factors up to 10**12 or so.
3. After that, use ECM and/or MPQS to finish.

You'll also need some sort of primality test available: the factors produced by most of these methods are not guaranteed to be prime, so may themselves need further factoring.

Answer 8

Pulled directly from my answer to this other question.

The method will work, but will be slow. "How big are your numbers?" determines the method to use:

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Richard Brent's modification of Pollard's rho algorithm.
• Less than 10^20: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve