- 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

> digit integer today? Sadly, the answer appears to remain

> "more than a lifetime."

your conclusion seems reasonably sound.

> Two methods come to mind: ECM would succesfully factor

Agreed.

> 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

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

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

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

This also applies to GNFS, though a more stringent restriction in

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

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

my lifetime!

Paul - << Previous post in topic Next post in topic >>