主題
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)。

另請參閱

合數問題, 素性測試

使用 探索

參考文獻

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. "素性測試很容易。" 頭條新聞, 2002 年 8 月 7 日。 https://mathworld.tw/news/2002-08-07/primetest/.

在 中被引用

AKS 素性測試

引用為

Weisstein, Eric W. "AKS 素性測試。" 來自 網路資源。 https://mathworld.tw/AKSPrimalityTest.html

主題分類