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

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

Expand Messages
  • Paul Leyland
    Apr 26, 2001
      > 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."

      I didn't see the question (are messages being dropped by the list?), but
      your conclusion seems reasonably sound.

      > 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
      > take about 8*10^24 times as long, or about 5*10^22 years!

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


      Paul
    • Show all 12 messages in this topic