Re: Newby Question?
- --- In firstname.lastname@example.org, James Wanless <james@g...> wrote:
> Décio Luiz Gazzoni Filho wrote:the
> > -----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
> _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
Distributed Factoring of 2^3326400-1