多项式时间伪确定性素数构造方法

《Journal of the ACM》：Polynomial-Time Pseudodeterministic Construction of Primes

随机算法构造素数和满足多项式时间密集性质字符串的伪确定性方法研究。通过无条件多项式时间随机算法B，在无限多次发生律下实现n位素数的高概率构造，并扩展至一般密集性质字符串的构造。

　　

摘要AI摘要

要查看此由AI生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

对于一个搜索问题，如果一个随机算法能够以高概率产生一个固定的、规范的解决方案，那么这个算法就是伪确定性的。在关于这个主题的开创性工作中，Gat和Goldwasser [16]提出了一个主要的未解决问题：是否可以在多项式时间内伪确定性地构造出质数。

我们在无限重复的情况下给出了这个问题的肯定答案。更具体地说，我们提供了一个无条件的多项式时间随机算法\(B\)，对于无限多的\(n\)值，\(B(1^n)\)能够以高概率输出一个规范的\(n\)位质数\(p_n\)。更一般地，我们证明了对于每一个可以在多项式时间内判断的字符串属性\(Q\)，都存在一种无限重复的、伪确定性的多项式时间构造方法来生成满足该属性的字符串。这改进了Oliveira和Sthanthanam [49]提出的亚指数时间构造方法。

我们的构造方法使用了几种新的思路，包括一种用于伪确定性构造的新颖自举技术，以及Chen和Tell [11]提出的均匀难度-随机性框架的定量优化方法，并使用了Shaltiel–Umans生成器的变体[51]。

AI摘要

AI生成的摘要（实验性）

此摘要是由自动化工具生成的，并非由文章作者编写或审核的。它旨在帮助发现新内容、帮助读者评估文章的相关性，并协助来自相关研究领域的读者理解文章内容。它旨在补充作者提供的摘要，后者仍然是文章的官方摘要。完整文章才是权威版本。点击这里了解更多。

点击这里对摘要的准确性、清晰度和实用性进行评论。您的反馈将有助于改进未来的摘要版本。

要查看此由AI生成的通俗语言摘要，您必须具有高级访问权限。