Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the fastest integer factorization algorithm?

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?

like image 455
Mithrax Avatar asked Feb 15 '10 16:02

Mithrax


People also ask

What is the fastest prime factorization algorithm?

The fastest-known fully proven deterministic algorithm is the Pollard-Strassen method (Pomerance 1982; Hardy et al. 1990).

How do you factor a number quickly?

The quickest way to find the factors of a number is to divide it by the smallest prime number (bigger than 1) that goes into it evenly with no remainder. Continue this process with each number you get, until you reach 1.

What is the fastest way to factor large numbers?

How to Find Factors of Large Numbers? To calculate the factors of large numbers, divide the numbers with the least prime number, i.e. 2. If the number is not divisible by 2, move to the next prime numbers, i.e. 3 and so on until 1 is reached.

How long does it take to factorize a number?

On average, finding a 12-digit factor of a 100-digit number takes about 1 min 40 s, finding a 15-digit factor of a 100-digit number takes about 10 min and finding an 18-digit factor of a 100-digit number takes about 50 min.


1 Answers

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
like image 151
Sam Harwell Avatar answered Sep 30 '22 14:09

Sam Harwell