math - What is the fastest integer 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

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^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve