ECCC-Report TR23-076https://eccc.weizmann.ac.il/report/2023/076Comments and Revisions published for TR23-076en-usWed, 24 May 2023 16:56:30 +0300
Paper TR23-076
| Polynomial-Time Pseudodeterministic Construction of Primes |
Lijie Chen,
Zhenjian Lu,
Igor Carboni Oliveira,
Hanlin Ren,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2023/076A 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.Wed, 24 May 2023 16:56:30 +0300https://eccc.weizmann.ac.il/report/2023/076