  In this paper, we analyze several variants of a simple method for generating
prime numbers with fewer random bits. To generate a prime $p$ less than $x$,
the basic idea is to fix a constant $q\propto x^{1-\varepsilon}$, pick a
uniformly random $a<q$ coprime to $q$, and choose $p$ of the form $a+t\cdot q$,
where only $t$ is updated if the primality test fails. We prove that variants
of this approach provide prime generation algorithms requiring few random bits
and whose output distribution is close to uniform, under less and less
expensive assumptions: first a relatively strong conjecture by H.L. Montgomery,
made precise by Friedlander and Granville; then the Extended Riemann
Hypothesis; and finally fully unconditionally using the
Barban-Davenport-Halberstam theorem. We argue that this approach has a number
of desirable properties compared to previous algorithms.
