Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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|improve this answer
3  
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
add comment

Your Answer

 
discard

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.