头条新闻

素性测试变得容易

作者：Eric W. Weisstein

2002 年 8 月 7 日——素数是指除了 1 和自身之外没有其他整数因数的整数。例如，6 不是 素数，因为它除了 1 和 6 之外还有因数 2 和 3。另一方面，7 是 素数，因为它的因数只有 1 和 7。不是素数的数字称为合数。

虽然素数简单易于描述和理解，但尽管自欧几里得和埃拉托斯特尼时代以来，它们一直是深入数学研究的主题，但素数的性质却出乎意料地难以捉摸。虽然欧几里得证明了存在无限多个素数（这个结果现在被称为欧几里得第二定理，出现在欧几里得著名的几何原本命题 IX.20 中），但确定一个给定的数字是素数还是合数，更不用说将其分解为所谓的素因数分解（如果是合数）已被证明是一个难题。由于素数在RSA 算法等加密算法中的广泛应用，这个问题近年来受到了极大的关注。例如，如果存在分解大数的有效算法，那么全球绝大多数加密电子通信将很容易被破解。

算法复杂度理论是一门数学学科，它根据问题求解的难度对问题进行分类。如果解决问题所需的步骤数受到问题规模的某个幂的限制，则该问题被分配到 P 类（其中“P”代表“多项式时间”）。如果一个问题允许非确定性解法，并且验证解法所需的步骤数受到问题规模的某个幂的限制，则该问题被分配到 NP 类（其中“NP”代表“非确定性多项式时间”）。素性测试（换句话说，在不实际计算任何因数的情况下确定一个数字是否为素数）比素因数分解更容易，并且长期以来一直被认为是 P 类问题。

今天已知的最有效的素因数分解和素性测试算法是概率性的，因为它们使用复杂的技术，几乎总是返回结果，但并非以绝对的数学确定性这样做。例如，Mathematica 的 PrimeQ 命令使用一种特别有效的概率算法，称为 Rabin-Miller 强伪素数测试来测试素性。

8 月 6 日，印度坎普尔印度理工学院的 M. Agrawal、N. Kayal 和 N. Saxena 发布了一份电子预印本，其中包含一种据称可以在多项式时间内测试素性的算法 (Agrawal et al. 2002)。该论文此前已分发给许多著名的数论学家。领先专家 Hendrik Lenstra（加州大学伯克利分校）和 Carl Pomerance（贝尔实验室）已经对该论文发表了评论，称其结果是正确的、巧妙的和优雅的（Clark 2002, Pomerance 2002）。虽然该算法的渐近时间复杂度已被证明对于整数 n 为 O(ln¹²n)（这意味着运行时间与被测数字的自然对数的 12 次方成正比），但启发式方法表明，在实践中，该算法的时间复杂度为 O(ln⁶n)，如果可以证明另一个数论猜想，则可以进一步降低到 O(ln³n)。

更快的素性测试不会对电子通信的安全性构成任何直接风险。然而，它确实为大大加快数论许多领域的数学计算开辟了可能性。现在断言新算法是否可以以能够与快速概率方法竞争的方式实现还为时过早。但是，作为一种权威地区分可能素数（根据某些测试或测试集看起来是素数，但无法严格确定其素数的素数）与实际素数的方法，它可能已经是目前最快的算法之一！