Paul,

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

Jack