Deterministic construction of an n-bit prime in time polynomial in n (current best 2^(n/2+o(n)))

Best known. Brute-force testing takes $N^{1+o(1)}$. The unconditional state of the art, due to Odlyzko and Lagarias–Odlyzko (computing $\pi(x)$ by an analytic method), takes $N^{1\mathrm{/}2+o(1}$ time to find a prime in . The Polymath4 project (2009–2010; Tao, Croot, Helfgott and other participants; arXiv:1009.3956, published in Math. Comp. 2012) aimed to beat the square-root barrier, and obtained partial results (for example computing the parity of the number of primes in an interval in about the same time) but did not break the barrier. Under the Riemann Hypothesis, prime gaps are at most , which gives the same exponent; Cramér's conjecture (gaps ) would give polynomial time but is unproven. A full derandomisation of (which follows from Impagliazzo–Wigderson-type circuit lower bounds) would give a polynomial-time algorithm.

A deterministic polynomial-time prime constructor would give the first unconditional derandomisation of an important randomised search problem and remove a randomness requirement in cryptographic key generation (a theoretical point only; random primes are used in practice). Partial progress with $N^{1/2-\delta}$ would require new ideas in analytic number theory.

Full resolution: a deterministic algorithm that on input $n$ outputs an $n$-bit prime in time $\mathrm{poly}(n)$, with proof. Partial progress: any deterministic algorithm beating the square-root barrier, i.e. time $2^{(1/2-\delta)n}$ for a fixed , or a pseudodeterministic polynomial-time construction that works for every .