# Dixon's Theorem to probabilistically bound largest factor of N

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.

-
Congrats on the 10K :-) –  Asaf Karagila Oct 14 '11 at 8:31
@Asaf: Thank you! –  mixedmath Oct 14 '11 at 13:38

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.

-
–  t.b. Jul 25 '11 at 11:46
@Theo Excellent. I knew I was going no where fast. Thank you for that. –  mixedmath Jul 25 '11 at 15:32