Deterministic prime construction

A prime is a whole number greater than one with no positive divisors except one and itself. Ask a computer for a prime with exactly three binary digits, written using only 0 and 1: 5, written 101, works because three-digit binary numbers run from 4 through 7. The general request specifies the number of digits. Can one fixed algorithm always produce a prime of that length, without random choices, in a number of steps bounded by a fixed power of the requested length, such as its square or cube? Quickly checking whether a chosen number is prime is a different task from choosing one.[1]

Can a single deterministic algorithm always construct a prime with exactly the requested number of binary digits in polynomial time? The input is the unary string $1^n$, meaning n copies of the symbol 1, with $n\geq2$. The output must be prime and satisfy $2^{n-1}\leq p<2^n$. For $n=3$, $p=5$ has binary representation 101 and lies in the required interval. Running time is bounded by $Cn^k$ for fixed constants C and k independent of n; no random bits or unproved number-theoretic hypothesis are allowed. A polynomial-time primality test checks a candidate but does not choose one. A pseudodeterministic construction still uses randomness, with high-probability agreement on a canonical output for each length where its success guarantee holds. That agreement concerns the answer rather than identical computational choices.[1]

Testing a candidate is fast; finding the candidate this way remains unresolved.[1] [2]

The cited prime-construction theorem supplies a polynomial-time pseudodeterministic algorithm with its success guarantee on infinitely many lengths, not a deterministic construction for every length. The 2026 preprint conditionally classifies a separate search task, Weak-Bertrand, for the much wider interval $(2^n,2^{32n})$. That conditional classification does not solve the exact n-bit target.[1] [2]

An existence argument says a suitable number is there; a checking algorithm recognizes it when someone supplies it. Neither automatically gives an efficient way to select it. This problem isolates that gap for a familiar mathematical object and asks whether random choices can be removed from the construction itself.[1]

Primes make the difference between verification and construction especially sharp: an output has a concise description and can be efficiently checked, yet finding one uniformly within the required time remains a separate demand. This is a test case for replacing randomness in search, where a program must deliver a mathematical object rather than only decide whether one exists. A solution would turn every binary-length request into a reproducible construction with a worst-case time guarantee. Density, reproducible randomized outputs and conditional classifications of other intervals each supply different information about that broader constructive aim.[1]