## 995RE: [PrimeNumbers] Re: Factor 500 digits?

Expand Messages
• Apr 26, 2001
> You asked how long it would take to factor a random 500

I didn't see the question (are messages being dropped by the list?), but

> 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.

Agreed.

> 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

Reasonable as far as it goes, but it goes off at a tangent!

Already we have a much better algorithm than MPQS. It's the general
number field sieve. The crossover point where GNFS becomes faster than
MPQS depends strongly on the quality of the implementation but seems to
lie somewhere in the range 100-140 digits.

> 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).

This also applies to GNFS, though a more stringent restriction in
practice would be the linear algebra phase.

All the above (both postings) assumes that there is no theoretical
breakthrough. A reasonably sound assumption, perhaps.

Approaching the question from a different direction: we can fit some
sort of plausible equation to the experimental data over the last few
decades since the development of sub-exponential factoring algorithms.
Once such equation I have to hand is Y = 1928 + 13D^(1/3) where Y is the
year of first factoring a D decimal digit integer. Sorry I can't give
credit to the originator but I don't have the reference equally to hand.

IF you're willing to make a completely wild prediction with very little
justification for its accuracy, plugging D=500 into this equation gives
2031 as the date when a 500-digit hard integer will be first factored.
I'm no spring chicken, but I have reasonable hopes that 2031 will be in