Polynomial-Time Pseudodeterministic Construction of Primes

by Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, and Rahul Santhanam

Oded's comments

I am very excited about this result.

In our world, where BPP=P is but a conjecture, which can be backed by intuition as well as by widely believed intractability conjecture, the distiction between PPT algorithms that solve search problems and ones that (whp) yield a canonical solution is a fundamental one. (Interestingly, this distinction is captured by the distiction between BPP and promise-BPP.)

An archetypical case that is of natural appeal is when the search problem is actually input-less; that is, the problem is actually one of generating an $n$-bit long object that satisfies some predetermined poly-time recognized property, when guaranteed that such objects are not rare. The straightforward algorithm that repeatedly selects random strings and tests them for the property solves this problem, alas does not provide a canonical solution (whp). Indeed, this randomized algorithm is a natural example of a randomized algorithm that solves a search problem but does not provide a canonical solution (whp); that is, it is not pseudodeterministic.

The current paper almost solves the problem, where the almost reservation refers to the fact that the algorithm works for infinitely many $n$'s (i.e., i.o.), but not necessarily for all $n$'s (i.e., .a.e.). Still, this is a notable step forwards, which improves over the previous algorithm, which had a sub-exponential time-bound (and also worked only i.o.).

The original abstract

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.

See ECCC TR23-076.

Back to list of Oded's choices.