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.

  • $\begingroup$ 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. $\endgroup$ – Peter Taylor Nov 18 '18 at 22:29
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 19 '18 at 3:08

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.