## 992Re: Factor 500 digits?

Expand Messages
• Apr 25, 2001
Paul,

You asked how long it would take to factor a random 500 digit integer

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

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
• Show all 12 messages in this topic