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

Re: Newby Question?

Expand Messages
  • elevensmooth
    ... the ... (effectively) ... To completely factor a number, as requested, you need to know the size of the SECOND LARGEST prime factor. I don t have Knuth s
    Message 1 of 4 , Jul 24, 2004
      --- In primenumbers@yahoogroups.com, James Wanless <james@g...> wrote:
      > D├ęcio Luiz Gazzoni Filho wrote:
      >
      > > -----BEGIN PGP SIGNED MESSAGE-----

      > >> Put another way what is the probability that I can completely a
      > >> factor randomly selected large integer on my PC within a few
      > >> minutes?


      > > Knuth develops an expression for that, in The Art of Computer
      > > Programming vol. 2, p. 382-383.

      > No, that's wrong - the expresion you cite is an investigation of
      the
      > _largest_ prime factor - whereas what was being asked was
      (effectively)
      > "how big is the _smallest_ prime factor?"

      To completely factor a number, as requested, you need to know the size
      of the SECOND LARGEST prime factor. I don't have Knuth's book handy,
      so I'm not sure if it there. But I know it is in Knuth's article.

      For some questions, such as analysis of ECM with stage 2, you need to
      know the simultaneous probability the second largest factor is less
      than "x" and the largest factor is less than "y". This is in
      Silverman and Wagstaff's paper, although the typesetter apparently
      made an error in setting the equation for mu.

      For the smallest factor, you need Merten's Theorem.

      ====================================
      Knuth & Pardo, "Analysis of a Simple Factorization Algorithm",
      Theoretical Computer Science 3 (1976), 3211-348

      Silverman and Wagstaff, "A Practical Analysis of the Elliptical Curve
      Factoring Algorithm," Mathematics of Computation Vol 61, No. 203
      (July, 1993) 445-462

      http://primes.utm.edu/glossary/page.php?sort=MertensTheorem

      William
      ================================
      http://ElevenSmooth.com
      Distributed Factoring of 2^3326400-1
    Your message has been successfully submitted and would be delivered to recipients shortly.