In a cryptographic lecture we just assumed that this statement holds. In particular, we said for a fixed length of bits one can always find two primes, that have the same length in binary representation. But why so? Is there an easy explanation I just overlooked or is the matter a bit more complicated?
I guess it follows from Bertrand's postulate, but I don't see how we get the second prime in this interval.
Edit: Of course this statement only holds for a large enough n, meaning $n\geq2$
Best Answer
This follows from a strengthening of Bertrand's postulate. In fact it can be shown that for every $\varepsilon>0$, for all sufficiently large $n$ there exists a prime between $n$ and $(1+\varepsilon)n$: See here.
In particular, for any $k$ there are at least $k$ primes between $2^n$ and $2^{n+1}$ for sufficiently large $n$.