# Distribution of the RSA numbers

Let's take a random prime $p$. For the sake of the argument let's say $\log(p)\approx 1000$. Let's suppose all numbers between $p$ and $p+1000^2$ are composites. What is the approximate probability that one of these numbers is product of two primes of exactly $217$ digits? ($217=\lfloor(\log_{10} p)/2\rfloor$

To simplify the answer, the probability can be given in terms of the prime counting function and its inverse, or any other number theoretic function which has a reasonably good approximation in terms of computing asymptotic probabilities.

Please note that my question is not about the behavior as $p$ tends to infinity. I already know the answer to that.

Edit: The assumption that all numbers between $p$ and $p+1000^2$ are composite seems to be false if $\log p \approx 1000$; this was stipulated in one the answers and dismissed as irreverent. The answers and the question should be taken in that light.

• Honestly,@user2943324 you don't seem to "get" how MSE works.You don't "own" your questions here. When a question is out there and get an answer it is suppose to be beneficial to the whole community. Your question is not only about yourself.This is a community. Please read up on how things work here. – John Smith Sep 30 '14 at 13:06

First of all, for all practical purposes your stipulation about a lack of primes above $p$ Just Doesn't Matter here — but note that it's actually very unlikely that none of them are; one would expect the 'next' prime to be on the order of $p+1000$, Cramer's conjecture says that the largest gap less than $p$ is of size proportional to $(\ln p)^2$, and a provisional gap of size roughly $1000^2$ is known between two provisional primes, but those numbers are of more than 40k digits.

The odds that a number $q$ of size $\approx\sqrt{p}\approx e^{500}$ is prime are roughly $\frac1{500}=.002$; this means that the odds a number of twice that size is a product of two primes of that size is roughly $\frac12(.002)^2 = 2\times 10^{-6}$ (with the factor of one-half because order of the two primes doesn't matter) and the odds that such a number isn't a product of two suitably-sized primes are roughly $1-(2\times 10^{-6})$. Now, these probabilities aren't all independent (since e.g. small factors on one number preclude the same small factors on 'nearby' numbers), but it's a very common number-theoretic assumption to presume that they're effectively so. Since we're looking at $10^6$ numbers, this means that the odds of not hitting such a number are roughly $\left(1-\frac{2}{N}\right)^N$, where $N=10^6$. But this should be a familiar-looking form from the exponential limit; this probability is very close to $e^{-2}\approx .135$. In other words, the odds of hitting a product of two appropriately-sized primes in the interval are roughly $86.5\%$.

Note that this is a relatively loose estimate; in particular, effects from the size of the intervals (you're ostensibly asking for primes of exactly 217 digits, not primes 'near $e^{500}$')should come into play. But for back-of-the-envelope purposes, this kind of calculation (done perhaps a bit more carefully than I have here!) — and in particular the 'local probability' and exponential estimate aspects of it — is the simplest way to approach a problem of this sort.

• Don't do it Steven! I get the same answer (98%) by a completely different method, so I'm sure it's right. – TonyK Sep 30 '14 at 12:03
• @user2943324: Steven's answer contains two errors that I can see: the powers of ten are out by 1, and the odds of a number etc. are half what he says. So I think the correct answer is closer to $80\%$. See my answer for details. – TonyK Sep 30 '14 at 12:33

Here is another approach to the original question, which asked (roughly): Given an interval of length $10^6$ in the range $[10^{432},10^{434})$, what is the probability that it contains a number of the form $pq$, where $p$ and $q$ are $217$-digit primes?

There are about $N=\frac{10^{217}}{217\ln 10}-\frac{10^{216}}{216\ln 10}\approx 1.792\times 10^{214}$ $217$-digit primes. So the number of products $pq$ of $217$-digit primes in the interval $[10^{432},10^{434})$ is $\frac12 N(N-1) \approx 1.606 \times 10^{428}$.

Thus the probability that a random number in the range $[10^{432},10^{434})$ is of the form $pq$ is about

$$P = 1.606 \times 10^{428} / (10^{434} - 10^{432}) \approx 1.622 \times 10^{-6}$$

Now we can refer to Steven Stadnicki's answer, to get that the probability of finding such a number in a million trials is about

$$1-(1-P)^{10^6}\approx1 - e^{-P \times 10^6} \approx 1 - e^{-1.622} \approx 0.8025$$

• @user2943324: I don't understand why you asked the question in the first place if you didn't want it answered. Anyway I enjoyed working it out, so I wanted to share my answer with people (not you, obviously). – TonyK Sep 30 '14 at 12:44
• I'll revise my answer; the key differences that lead to the difference in probabilities are (a) the factor of two due to order-of-factors that I Just Plain Missed, and (b) the difference between 'probability that a random number near $x$ is prime' and 'probability that a random number in $[x, x+y]$ is prime' - basically, the difference between a derivative and a modestly-sized finite difference. – Steven Stadnicki Sep 30 '14 at 15:33
• (and this is an excellent answer, of course, covering the interval-size effects that I skipped over.) – Steven Stadnicki Sep 30 '14 at 15:46
• And now the difference between our two answers can be put down to the fact that you are answering the (original) question, where $p \approx e^{1000}$, and I am answering my own version of it, where $p \in [10^{432},10^{434})$. – TonyK Sep 30 '14 at 15:47