# Efficient sampling of primes

Using rejection sampling, it is trivial to construct a Las Vegas algorithm for sampling a uniformly random prime number less than a given $$N$$. What is known about sampling algorithms that run in worst-case polynomial time and produce the exact uniform distribution on primes? More generally, when an efficient testing for a property is available, is there a method better than rejection sampling that would achieve worst case polynomial time exactly-uniform sampling? This seems like a classical problem (related to sampling vs counting) but I'm not sure where to look up.

• Worst-case polynomial? No such thing is known even remotely. There is no known polynomial-time algorithm that given $N$, computes a prime between $N$ and $2N$. Oct 15, 2020 at 6:05
• Not to mention that no randomized algorithm with any worst-case bound whatsoever on the running time can produce exactly even the uniform distribution on $3$ elements. The distribution produced by any such algorithm has all probabilities integer multiples of $2^{-t(n)}$, where $t(n)$ is the bound on running time. Oct 15, 2020 at 7:27
• Fair enough. One has to look for an idealized model where such issues can be circumvented. Oct 15, 2020 at 16:06
• @EmilJeřábek: What if you allow the random source to return a uniformly random number in the range ${1..n}$ for any input natural $n$? Then you can produce any rational probability distribution with finite support in $O(1)$ time. Oct 21, 2020 at 7:12