如何构建大素数 | 广达杂志

质数是很棘手的事情。 我们在学校里了解到，它们是除了 1 和它们本身之外没有因数的数字，而且数学家几千年来就知道它们存在无限多个。 按照命令生产一个似乎并不困难。

但它是。 构造任意大的素数非常复杂。 基本上你有两种计算选择，两者都有缺点。 你可以利用随机性并通过猜测找到一个素数，但这种方法是不一致的——你每次都会冒着生成不同素数的风险。 或者您可以使用更可靠、确定性的算法，但计算成本很高。

五月，一个计算机科学家团队 显示 一种混合方法也可以发挥作用。 他们发布了一种算法，该算法有效地结合了随机和确定性方法来输出特定长度的素数，即使该算法运行多次，也很有可能输出相同的素数。 该算法以有趣的方式将随机性和复杂性联系起来，它也可能对密码学有用，因为密码学中的一些编码方案依赖于大素数的构造。

“他们提出了一系列的尝试，每个尝试都试图构造一个不同长度的素数，并表明其中一个尝试是有效的，”说 罗伊泰尔是高等研究院的理论计算机科学家，他没有参与这项工作。 “这是一种输出确定性选择的素数的结构，但允许你在这个过程中扔硬币并做出随机选择。”

制定有效的素数配方的挑战有着深刻的根源。 研究伪随机算法的奥弗·格罗斯曼（Ofer Grossman）说：“我们真的不太了解素数是如何分布的，或者素数之间的差距。” 如果我们不知道在哪里可以找到它们，就没有简单的方法从头开始生成素数。

随着时间的推移，研究人员开发了上述方法。 最简单的方法就是猜测。 例如，如果您想要一个 1,000 位的素数，您可以随机选择一个 1,000 位的数字，然后检查它。 “如果它不是素数，你只需尝试另一个，另一个，依此类推，直到找到一个，”说 拉胡尔桑塔南牛津大学计算机科学家，也是这篇新论文的合著者。 “因为素数有很多，所以在相对少量的迭代之后，这个算法就会给你一些很有可能是素数的数字。” 但使用随机性意味着你每次可能都会得到不同的数字，他说。 如果您需要一致性，那么这可能是一个问题 - 例如，如果您正在采用依赖于大素数可用性的加密安全方法。

另一种方法是采用确定性算法。 您可以选择一个起点并开始顺序测试数字的素数。 最终你注定会找到一个，并且你的算法将始终输出你找到的第一个。 但这可能需要一段时间：如果您正在寻找 1,000 位的质数，即使是 2 的计算⁵⁰⁰ 这些步骤——这将花费比宇宙年龄更长的时间——并不足以保证成功。

2009年，数学家、菲尔兹奖得主陶哲轩想要做得更好。 他向数学家提出挑战，要求他们提出一种确定性算法，在计算时间限制内找到给定大小的素数。

该时间限制称为多项式时间。 如果算法所采取的步骤数不超过以下多项式函数，则该算法可以在多项式时间内解决问题 n，输入的大小。 （多项式函数包括将变量提升为正整数幂的项，例如 n² 或4n³.) 在素数构造的背景下， n 指的是你想要的素数的位数。 从计算角度来说，这并不需要花费太多：计算机科学家将可以通过算法在多项式时间内解决的问题描述为很容易。 相比之下，一个难题需要指数时间，这意味着它需要许多由指数函数近似的步骤（其中包括诸如 2ⁿ).

几十年来，研究人员一直在研究随机性和硬度之间的联系。 如果你允许随机性，并且对每次收到不同的数字感到满意，那么素数构造问题就会被认为很容易，但如果你坚持确定性，那么素数构造问题就会被认为很困难。

目前还没有人能够应对陶的挑战，但新作品已经很接近了。 它很大程度上借鉴了麻省理工学院计算机科学家 Shafi Goldwasser 和 Eran Gat 于 2011 年提出的方法。 他们描述了“伪确定性”算法——搜索问题的数学秘诀，比如寻找大素数，它可以利用随机性的好处，并且每次仍然以很高的概率产生相同的答案。 他们将利用配方​​中随机位的效率，这将在结果中去随机化，从而显得确定性。

从那时起，研究人员就一直在探索伪确定性算法。 2017年，华威大学的Santhanam和Igor Oliveira（他也对新工作做出了贡献） 描述 一种构造素数的伪确定性方法，使用随机性，看起来具有令人信服的确定性，但它在“次指数”时间内起作用——比指数时间快，但比多项式时间慢。 然后在 2021 年，泰尔和 陈丽杰，加州大学伯克利分校的计算机科学家， 探讨 如何使用难题来构建伪随机数生成器（一种生成与随机输出无法区分的数字字符串的算法）。 “[我们]发现了硬度和伪随机性之间的新联系，”陈说。

这些碎片终于在 2023 年春天整合在一起， 计算复杂性训练营 在伯克利西蒙斯计算理论研究所，研究人员开始共同研究这个问题，将过去的结果编织在一起。 Chen 表示，对于这项新工作，牛津大学计算机科学家兼合著者 Hanlin Ren 提出了以新颖的方式将 Chen-Tell 结果与 Santhanam-Oliveira 方法结合起来的初步想法。 然后，整个团队更充分地发展了这些想法，以产生新的论文。

桑塔南说，由此产​​生的伪确定性算法使用了查看过去工作的新方法，在多项式时间内生成素数。 事实证明，它使用随机性来输出特定长度的素数，并且该工具比随机猜测更准确，并且比确定性处理的计算效率更高。

桑塔南说，新算法也非常简单，它可以应用于广泛的搜索问题——实际上，可以应用于任何密集的数字子集，比如素数，可以在多项式时间内确定其成员资格。 但它并不完美。 该算法适用于无限多个输入长度，但它不涵盖所有数字长度。 可能仍然存在一些值 n 算法无法确定地产生素数。

“摆脱这个小警告会很酷，”格罗斯曼说。

桑塔南说，最终目标是找到一种根本不需要随机性的算法。 但这一探索仍然悬而未决。 “我们想要使用决定论，”他说。

但他也指出，伪随机过程是强大的工具，像构造素数这样的项目只是使用它们来连接数学、计算机科学、信息论和其他领域的想法的一种方式。

泰尔说：“尝试思考这些精彩的观察结果还会带来什么结果，真是令人兴奋。”