992Re: Factor 500 digits?
- Apr 25, 2001Paul,
You asked how long it would take to factor a random 500 digit integer
today? Sadly, the answer appears to remain "more than a lifetime."
Two methods come to mind: ECM would succesfully factor such a number
if all but one of the prime factors are "small" (less than about 50
digits). This will not happen very often.
The other method (for general numbers): MPQS is a powerful method for
use with general numbers (those not of the form a^n+b, with small a & b).
MPQS has a running time of the order O(exp(sqrt(log(n)*log(log(n))))),
where n is the number to be factored. I'm currently running an MPQS
program on an 88-digit number; I expect the program to take around
54 hours on my 450 MHz PC. Run the numbers: a 500-digit number will
take about 8*10^24 times as long, or about 5*10^22 years!
There are other problems with using MPQS to factor such a number;
the size of the sieve array created would be greater than any computer
could hope to handle (probably greater than all of the computer memory
in all the computers in the world combined).
I'm sure that some can point to examples of numbers in the 500-digit
range which have been completely factored; many examples do exist --
however, these numbers either have a special form permitting algebraic
factorization (such as 10^540-1), or they satisfy the requirements
above for an ECM factorization (only one large prime factor), such as:
10^499+47 == 3 * 29 * 2938069 * P491
- << Previous post in topic Next post in topic >>