The recently published April 2026 issue of the Journal of the ACM contains a paper by Chen, Lu, Oliveira, Ren, and Santhanam (Chen et al. 2026), in which the authors present a “pseudodeterministic” construction of prime numbers in the infinitely-often regime.
An improtant algorithmic task in number theory is the task of constructing primes. Given a positive integer as input, we would like an algorithm that runs in time polynomial in and returns an -digit prime. There is an obvious randomized algorithm for this task: generate random -digit integers, test them for primality (this can be done in polynomial time (Agrawal et al. 2004)), and output the first prime found. Since the proportion of primes among -digit integers is about for some constant , it is easy to check that, with high probability, only polynomially many integers need to be tested. The drawback is that different runs of this algorithm on the same input are likely to return different primes.
A major open problem is to develop a deterministic polynomial-time algorithm for this task. Such an algorithm would, for each , return a specific prime . A well-believed conjecture of Cramér states that there is a constant such that every sequence of consecutive -digit positive integers contains a prime. If this conjecture is true, then one can simply test the first -digit integers in order until the first prime is found, and the running time will be polynomial in . However, Cramér’s conjecture is very difficult, and the current best upper bound on the gap between consecutive primes (Baker et al. 2001) is exponential in the number of digits.
Motivated by this difficulty, Gat and Goldwasser (Gat and Goldwasser 2011) introduced the concept of pseudodeterministic algorithms. These are randomized algorithms that, with high probability, return the same correct answer on each fixed input. The main open question raised in (Gat and Goldwasser 2011) asks whether such an algorithm exists for prime construction: for each given , it should run in time polynomial in and, with high probability, output a specific -digit prime . In 2026, Chen, Lu, Oliveira, Ren, and Santhanam (Chen et al. 2026) proved that this can be done for infinitely many input lengths.
The proof of Theorem applies not only to prime generation, but more generally to any problem whose set of valid outputs is both dense and easy to recognize. Here dense means that the proportion of correct outputs among strings of length is at least for some constant , while easy to recognize means that there is a deterministic polynomial-time algorithm for checking whether a proposed output is correct. Prime numbers satisfy these two conditions: they are dense by the prime number theorem and easy to recognize by (Agrawal et al. 2004). Of course, the set of all primes is not the only set with these properties. For example, an analogue of Theorem holds for generating primes congruent to modulo , for any fixed coprime integers and .