--- 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