Browse Groups

• ... 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
View Source
--- 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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.