EUVIMEDEUVIMED entdecken
Crossref

Polynomial-Time Pseudodeterministic Construction of Primes

Lijie Chen, Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

Journal of the ACM · 30.04.2026 · 73 (2) · 1-43

DOI: 10.1145/3803408 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 23.04.2026. Verfasst von Lijie Chen und 4 weiteren Autor:innen. Die Arbeit nennt 60 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 [ 16 ] 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 [ 49 ]. 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 [ 11 ], using a variant of the Shaltiel–Umans generator [ 51 ].

Zitieren

APA

Chen, L., Lu, Z., Oliveira, I., Ren, H., & Santhanam, R. (2026). Polynomial-Time Pseudodeterministic Construction of Primes. Journal of the ACM, 73(2), 1-43. https://doi.org/10.1145/3803408

Vancouver

Chen L, Lu Z, Oliveira I, Ren H, Santhanam R. Polynomial-Time Pseudodeterministic Construction of Primes. Journal of the ACM. 2026;73(2):1-43. doi:10.1145/3803408

BibTeX
@article{Chen2026,
  author = {Chen, Lijie and Lu, Zhenjian and Oliveira, Igor and Ren, Hanlin and Santhanam, Rahul},
  title = {Polynomial-Time Pseudodeterministic Construction of Primes},
  journal = {Journal of the ACM},
  year = {2026},
  volume = {73},
  number = {2},
  pages = {1--43},
  doi = {10.1145/3803408}
}
Kostenlos starten →