6
$\begingroup$

I have recently decided to read up on the current integer factorization algorithms. When looking into some of the algorithms, I came across the following statement:

Say that p is the smallest prime factor of n. By Dixon's Theorem, the probability that the largest factor of n is less than $(p)^\epsilon$ is roughly $\epsilon ^ {- \epsilon}$.

But when I hear Dixon's Theorem, I think of this. I currently don't see how Dixon's Theorem yields such a probabilistic bound. Can you help me with that?

And the disclaimer - I am not currently in any class, so this was not assigned to me, it is not a homework problem, and I will in no way be receiving any sort of academic credit for this work.

  • 0
    Congrats on the 10K :-)2011-10-14

1 Answers 1

2

Wrong Dixon! Please look at this link to get a start. Unfortunately, the relevant original paper (Mathematics of Computation 36, 1981, pp 255-260) is behind a pay wall unless you are at a subscribing university.

  • 3
    [The AMS offers it for free](http://dx.doi.org/10.1090%2FS0025-5718-1981-0595059-1).2011-07-25