Randomly Choosing a N-Bit Prime

Question

I've been studying some number theory, and I came across this problem:

Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$.

Consider the following algorithm to choose a random n-bit prime:

1) Pick a random n-bit number $k$.

2) Run a primality test on $k.$

3) If it passes the test, output $k$; else repeat the process.

Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.

I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.

But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.

I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.

Answer 1

Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.

Answer 2

It doesn't follow from the Lagrange’s prime number theorem alone.

That theorem alone would still allow for example no primes between $2^n$ and $2^{n+1}$ if n is even, and accordingly more if n is odd. So if you pick an even n, the algorithm could run forever. (It won't, but it doesn't follow from this theorem).

There is a stronger theorem that with π(N) := "Number of primes ≤ N", the limit of (N / ln N / pi(N)) = 1. From this theorem it follows that for large n, there are more than $2^n / n$ primes between $2^n$ and $2^{n+1}$ (note ln = base - e), so picking a random number in this range has probability > 1/n for picking a prime.

Let E be the expected number of attempts. You either find a prime in the first attempt, or within 1+E attempts. E = (1/n) + (1 - 1/n)(1+E), or E = (1/n) + 1+E - 1/n - E/n, or E/n = (1/n) + 1 - 1/n or E = n.