主题
Search

AKS 素性测试

2002 年 8 月，M. Agrawal 及其同事宣布了一种确定性算法，用于判断一个数字是否为素数，该算法以多项式时间运行 (Agrawal et al. 2004)。虽然长期以来人们一直认为这是可能的 (Wagon 1991)，但以前没有人能够提出明确的多项式时间确定性算法（尽管已知概率算法似乎以多项式时间运行）。该测试现在被称为 Agrawal-Kayal-Saxena 素性测试、分圆 AKS 测试或 AKS 素性测试。

P. Leyland 在评论这项发现的影响时指出：“数学界兴奋的原因之一不仅在于该算法解决了一个长期存在的问题，还在于它以一种非常简单的方式做到了这一点。现在每个人都在想，还有什么类似的问题被忽视了”（引自 Crandall 和 Papadopoulos 2003）。

Agrawal et al. (2004) 原始算法的复杂度为 O(ln^(12+epsilon)p)，但此后已大大降低，对于一般整数降至 O(ln^(6+epsilon)p) (Lenstra 和 Pomerance 2003)，或者对于某些整数或算法可能返回不明确结果的极小机会降至 O(ln^(4+epsilon)p) (Crandall 和 Papadopoulos 2003)。

另请参阅

合数问题, 素性测试

使用 Wolfram|Alpha 探索

参考文献

Agrawal, M.; Kayal, N.; and Saxena, N. "素数属于 P 类。" Ann. Math. 160, 781-793, 2004. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. 行动中的实验数学。 Wellesley, MA: A K Peters, p. 58, 2007.Bernstein, D. J. "Agrawal-Kayal-Saxena 素性证明定理的阐述。" 预印本。2002. http://cr.yp.to/papers/aks.ps.Bernstein D. J. "在 Agrawal-Kayal-Saxena 之后证明素性。" 预印本。2003 年 1 月 25 日。 http://modular.ucsd.edu/edu/Spring2004/129/references/primes/Bernstein-Proving%20primality%20after%20Agrawal-Kayal-Saxena.pdf.Bernstein D. J. "在本质上四次期望时间内证明素性。" 预印本。2003 年 1 月 28 日。Berrizbeitia, P. "为一大类数字改进“素数属于 P 类”。" 预印本。2002 年 11 月 20 日。Borwein, J. and Borwein, P. B. Pi 与 AGM：解析数论与计算复杂性研究。 New York: Wiley, p. 6, 1987.Borwein, J.; Bailey, D.; and Girgensohn, R. 数学实验：通往发现的计算路径。 Wellesley, MA: A K Peters, 2004.Bornemann, F. "素数属于 P 类：面向“普通人”的突破。" Notices Amer. Math. Soc. 50, 545-552, 2003.Clark, E. "多项式时间素性测试。" sci.math 新闻组帖子。2002 年 8 月 6 日。Crandall, R. and Papadopoulos, J. "关于 AKS 类素性测试的实现。" 2003 年 3 月 18 日。 http://developer.apple.com/hardware/ve/pdf/aks3.pdf.Crandall, R. and Pomerance, C. 素数：计算视角，第二版。 New York: Springer-Verlag, 2005. Germundsson, R.; Lichtblau, D.; and Terr, D. "Agarwal-Kayal-Saxena 素性测试。" http://library.wolfram.com/infocenter/Demos/4956/.Granville, A. "很容易确定给定的整数是否为素数。" Bull. Amer. Math. Soc. 42, 3-38, 2005.更新链接印度理工学院。“素数属于 P 类。” http://www.cse.iitk.ac.in/news/primality.htmlKayal, N. and Saxena, N. "迈向确定性多项式时间测试。" 技术报告。坎普尔，印度：印度理工学院，2002 年。 http://www.cse.iitk.ac.in/research/btp2002/primality.html.Lenstra H. W. Jr. "使用分圆环进行素性测试。" 预印本。2002 年 8 月 14 日。Lenstra H. W. Jr. and Pomerance C. "使用高斯周期进行素性测试。" 手稿。2003 年 3 月。Pomerance, C. "Agrawal、Kayal 和 Saxena 的分圆环测试。" 预印本。2002 年。Pomerance, C. "回复：新的多项式时间素性测试？" 2002a 年 8 月 7 日。 http://listserv.nodak.edu/scripts/wa.exe?A2=ind0208&L=NMBRTHRY&F=&S=&P=956.Pomerance, C. "一种新的素数筛选法。" FOCUS: Newsletter of the Math. Assoc. Amer. 22, No. 8, 4-5, 2002.Robinson, S. "据称新方法解决了数学中的关键问题。" 纽约时报，p. A16, 2002 年 8 月 8 日。Wagon, S. Mathematica 在行动。 New York: W. H. Freeman, pp. 15-17, 1991.Weisstein, E. W. "素性测试很容易。" MathWorld 头条新闻, 2002 年 8 月 7 日。 https://mathworld.net.cn/news/2002-08-07/primetest/.

在 Wolfram|Alpha 中被引用

AKS 素性测试

引用为

Weisstein, Eric W. "AKS 素性测试。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/AKSPrimalityTest.html

主题分类