Suppose I have been given positive numbers $n,m$, $n<m$, and an integer $N$. What is the probability that $N$ has a prime factor between $[n,m]$? I have heard about the prime number theorem but I'm not sure how can I apply it to this problem if I can apply it at all.

  • $\begingroup$ If $N<n$ then the probability is zero. $\endgroup$ – Dietrich Burde Sep 6 '14 at 20:52
  • $\begingroup$ That depends on the distribution of $N$. $\endgroup$ – JimmyK4542 Sep 6 '14 at 20:58
  • $\begingroup$ This question is not going to have a nice answer. Do you really need to pose it in such generality? There might be some hope of answering a much more restricted question, like how many 200 digit numbers are not prime but have no factors of less than 90 digits (highly relevant to cryptography). $\endgroup$ – almagest Sep 6 '14 at 21:26
  • $\begingroup$ I decided to put the question in general form to see how much we can achieve results like that. Originally I would like to know what is the probability that the general number field sieve would find a new factor to $2^{2^{12}}+1$. $\endgroup$ – guest Sep 7 '14 at 7:48

If $N$ is large compared to $m$, and $n>2$ is not too near to $m$, then the number of primes is asymptotically expected to be $$\sum_{n\le p\le m}\frac1p\sim\log\log m-\log\log n.$$

You can treat finding a factor as a Poisson event, making your chance of finding a factor in that range approximately $$1-\exp(-(\log\log m-\log\log n))=1-\log n/\log m.$$

  • $\begingroup$ This looks more like the expected number of prime factors in that range that divide N. The probability should be about $1-\prod_{n\leq p\leq m} \left( 1-\frac{1}{p} \right) $, shouldn't it? $\endgroup$ – Michael Stocker Sep 30 '14 at 11:28
  • $\begingroup$ @MichaelStocker: You're right -- I was supposing that the probability was small enough that the two are basically the same. I'll edit in the case where the probability is large. $\endgroup$ – Charles Sep 30 '14 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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