The Library
Polynomial-time pseudodeterministic construction of primes
Tools
Chen, Lijie, Lu, Zhenjian, Oliveira, Igor C., Ren, Hanlin and Santhanam, Rahul (2023) Polynomial-time pseudodeterministic construction of primes. In: 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023, Santa Cruz, CA, USA, 06-09 Nov 2023. Published in: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) ISBN 9798350318951. doi:10.1109/FOCS57990.2023.00074 ISSN 1523-8288.
|
PDF
WRAP-Polynomial-time-pseudodeterministic-construction-primes-23.pdf - Accepted Version - Requires a PDF viewer. Download (1136Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS57990.2023.00074
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 [1] 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(1n) outputs a canonical n-bit prime pn 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 [2]. 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 [3], using a variant of the Shaltiel-Umans generator [4].
Item Type: | Conference Item (Paper) | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Numbers, Prime, Polynomials, Algorithms | ||||||||||||||||||
Journal or Publication Title: | 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) | ||||||||||||||||||
Publisher: | IEEE | ||||||||||||||||||
ISBN: | 9798350318951 | ||||||||||||||||||
ISSN: | 1523-8288 | ||||||||||||||||||
Official Date: | 22 December 2023 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
DOI: | 10.1109/FOCS57990.2023.00074 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 18 September 2023 | ||||||||||||||||||
Date of first compliant Open Access: | 25 January 2024 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | 64th IEEE Symposium on Foundations of Computer Science (FOCS) 2023 | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Santa Cruz, CA, USA | ||||||||||||||||||
Date(s) of Event: | 06-09 Nov 2023 | ||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year