# Randomly Choosing a N-Bit Prime

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.

• Careful with your language. Each event is Bernoulli. It's the way you combine Bernoulli events which gives a binomial RV, a geometric RV, etc. – Peter Taylor Nov 18 '18 at 22:29
• Please credit the original source in the question. Whenever you quote from another source, you are supposed to provide proper attribution. That helps people answer your question as well. – D.W. Nov 19 '18 at 3:08

## 2 Answers

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.

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.