Can I select a large random prime using this procedure? Say I want a random 1024-bit prime $p$.  The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests.

But suppose instead that I do this:


select random odd 1024-bit number $n$
if $n$ is prime, return $n$
$n \leftarrow n+2$
goto 2


(This approach allows faster selection of primes via sieving.)

Since primes are not uniformly distributed on the number line, it would seem that this algorithm prefers primes that lie after long runs of composites.  Take a piece of the number line around $2^{1024}$ with x denoting a prime:


  ---x-x----------------------------x------------------------x---x


Clearly our algorithm above is much more likely to find the 3rd prime above than to find the 2nd one.

Question: Is this a problem?
This procedure is known as incremental search and his described in the Handbook of Applied Cryptography (note 4.51, page 148). Although some primes are being selected with higher probability than others, this allows no known attacks on RSA; roughly speaking, incremental search selects primes which could have been selected anyway and there are still gazillions of them. OpenSSL uses this prime generation technique.