choose two prime numbers of length $k$

Question

Maybe the following is a stupid question, if it is I apologize, and I encourage you to close my post.

Suppose that I want to encrypt a message with the RSA cryptosystem; the starting rule is the following: take two prime numbers $p$ and $q$ with $p\neq q$ such that, written as bit strings, they both have exactly $k$ digits. Now if the number of digits $k$ is fixed, who ensures that we can find two primes can be represented with $k$ digits? It is reasonable that if $k$ is big then there are always such two numbers, but is there a formal theorem that says this?

Thanks id advance.

Answer 1

Ramanujan showed that for every $k\in\mathbb{N}$ there exist an $N$ such that for every $n>N$ the numbers of primes between $\displaystyle\frac{n}{2}$ and $n$ is st least $k$, in the specific case for $k=2$ he showed that for every $n\ge11$ there are at least $2$ primes between $\displaystyle\frac{n}{2}$ and $n$.

These numbers are known as Ramanujan's primes (OEIS A104272)

Answer 2

There is an old theorem called Betrand's postulate that asserts that there is always a prime between $n$ and $2n$ for $n\geq 2$.

There are lots of refinements of this result - it is a fairly minimal one.

For example: "In 1976, Lowell Schoenfeld showed that for $n \geq 2010760$, there is always a prime between $n$ and $(1 + 1/16597)n$ ." This means that there at least $11,000$ primes between $n$ and $2n$ for $n\geq 2010760$.

In reality, there are almost certainly way more primes than this. A crude estimate:

$$\frac{2n}{\log 2n}-\frac{n}{\log n} = \frac{n\log(n/2)}{\log n\log 2n}\approx \frac{n}{\log 2n}$$ when $n$ is in the large range.

Answer 3

Indeed, no refinement of the Bertrand's postulate is needed. By taking in turn $n=10^k$, $n=2\cdot10^k$ and $n=4\cdot10^k$ you know that there are actually at least 3 primes between $10^k$ and $8\cdot10^k$, all of which have of course $k$ digits.

Answer 4

Not a proof here, but the likelihood of an arbitrary integer $n > 1$ being prime is $\dfrac1{\ln n}$ (by the prime number theorem). So over the range of n-bit integers $2^n \le x < 2^{n=1}$, you are overwhelmingly likely to have at least

$$\sum_{2^n \le i < 2^{n+1}} \frac{1}{\ln i} > 2^n\left( \frac{1}{\ln 2^{n+1}} \right) = \frac{2^n}{(n+1)\ln 2}$$ primes.