Finding primes with O(k) random bits

We have at least two ways to find k-digit primes with probability > 1/2 (say) in polynomial time using O(k) random bits. (Note that the trivial algorithm of randomly generating k-digit numbers and testing them for primality would require [math]\displaystyle{ O(k^2) }[/math] random bits, since one expects to need about k trials to get a hit.)

First method

There is a general-purpose method that would find any element of a dense, testable set of k-digit numbers using O(k) random bits.

This is a corollary of the unconditional pseudorandom generator of Nisan and Zuckermann, because the algorithm to choose a random n-bit prime uses space O(n). This PRG uses a random O(S) bit seed and outputs poly(S) bits which appear random to any space(S) machine (S>log n).

http://www.cs.utexas.edu/~diz/pubs/space.ps

(More explanation needed here!)

Second method

Let x be a random k-bit integer. We can search all the elements of [x,x+k] for primes in polynomial time, and this uses O(k) random bits. If we let X be the number of primes in [x,x+k], then this algorithm works as long as X is positive. So it suffices to show that X is positive with probability bounded away from zero (if it is less than 1/2, we can bring it to exceed 1/2 by iteration).

The expectation of X is comparable to 1 (prime number theorem) and the second moment of X is O(1) (this can be seen from a bit of sieve theory, in fact all moments are bounded). This establishes the claim.