Loading ...
Sorry, an error occurred while loading the content.

992Re: Factor 500 digits?

Expand Messages
  • Jack Brennen
    Apr 25, 2001
    • 0 Attachment
      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
    • Show all 12 messages in this topic