Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Congrats on the 10K :-) – Asaf Karagila Oct 14 '11 at 8:31
@Asaf: Thank you! – mixedmath Oct 14 '11 at 13:38
up vote 2 down vote accepted

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.

share|cite|improve this answer
The AMS offers it for free. – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.