What is the fastest integer factorization algorithm?

Mithrax picture Mithrax · Feb 15, 2010 · Viewed 61k times · Source

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

Sam Harwell picture Sam Harwell · Feb 16, 2010

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: