Close to Uniform Prime Number Generation With Fewer Random Bits

Pierre-Alain Fouque, Mehdi Tibouchi

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…