$p=k n+1$ prime This is a part of the question from CLRS (Introduction to Algorithms) Chapter on FFT and Polynomials. I am self reading and am stuck at this part. 
Let $n$ be a power of 2.
Suppose that we search for the smallest $k$ such that $p = kn + 1$ is prime. Give a simple heuristic argument why we might expect $k$ to be approximately $\ln n$. (The value of $k$ might be much larger or smaller, but we can reasonably expect to examine $O(\log n)$ candidate values of $k$ on average.)
My gut feeling is it has got to do something with the proof that there are infinitely many primes, but I am not sure if that is correct approach or build on that.

If $n$ is a large number, the probability that $kn+1$ is prime is about $\frac{2}{log(kn+1)}$, because $kn+1$ is odd. Note that $log(kn+1)\approx log(k)+log(n)\approx log(n)$ , so we can expect to be succesful after about $\frac{log(n)}{2}=O(log(n))$ trials.
