A randomized algorithm for a search problem is pseudodeterministic if it
produces a fixed canonical solution to the search problem with high
probability. In their seminal work on the topic, Gat and Goldwasser posed
as their main open problem whether prime numbers can be pseudodeterministically
constructed in polynomial time.
We provide a positive solution to this question in the infinitely-often
regime. In more detail, we give an unconditional polynomial-time
randomized algorithm B such that, for infinitely many values of n, B(1^n)
outputs a canonical n-bit prime p_n with high probability. More generally,
we prove that for every dense property Q of strings that can be decided in
polynomial time, there is an infinitely-often pseudodeterministic
polynomial-time construction of strings satisfying Q. This improves upon a
subexponential-time construction of Oliveira and Santhanam.
Our construction uses several new ideas, including a novel bootstrapping
technique for pseudodeterministic constructions, and a quantitative
optimization of the uniform hardness-randomness framework of Chen and
Tell, using a variant of the Shaltiel-Umans generator.
Reference: https://eccc.weizmann.ac.il/report/2023/076/
