AKS質數測試（又被稱為Agrawal–Kayal–Saxena質數測試和Cyclotomic AKS test）是一個決定型質數測試演算法 ，由三個來自印度坎普爾理工學院（英语：Indian Institute of Technology Kanpur）的計算機科學家，曼寧德拉·阿格拉瓦爾（英语：Manindra Agrawal）、尼拉吉·卡亞爾（英语：Neeraj Kayal）和尼汀·沙克謝納（英语：Nitin Saxena），在2002年8月6日發表於一篇題為質數屬於P的論文。[1]作者們因此獲得了許多獎項，包含了2006年的哥德爾獎和2006年的富尔克森奖。這個演算法可以在多項式時間之內，決定一個給定整數是質數或者合數。
若存在整數a > 0 且b > 1 ，令 n = ab ；則輸出「合數」。 for ( b = 2; b < = log2(n); b + + ){ a = n1/b; If ( a是整數 ) 輸出「合數」; } // a = n1/2...n1/4 = {5.568, 3.141, 2.360}，計算結果不是整數
找出最小的 r 令 ordr(n) > log2(n)。 nextR = True; r = 1; while ( nextR = = True ) { r + + ; nextR = False for ( k = 1;(!nextR) &&k ≤ log2(n); k + + ){ nextR = (nk % r = = 1 || nk % r = = 0); } } // 計算結果為：r = 29
若 對某些a ≤ r，1 < gcd(a,n) < n，輸出「合數」。 for ( a = r; a > 1; a-- ){ If ( 1 < gcd(a,n) < n ) 輸出「合數」; } // gcd(29,31) = 1, gcd(28,31) = 1, ..., gcd(2,31) = 1，計算結果為找不到符合的a使得1 < gcd(a,n) < n為真
若 n ≤ r, 輸出「質數」。 If ( n ≤ r ) 輸出「質數」; // 31 > 29，計算結果n比r大
^ 1.01.11.2Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P （页面存档备份，存于互联网档案馆）", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
^亨德里克·倫斯特拉 and Carl Pomerance, "Primality Testing with Gaussian Periods （页面存档备份，存于互联网档案馆）", preliminary version July 20, 2005.
延伸閱讀
Dietzfelbinger, Martin. Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P. Lecture Notes in Computer Science 3000. Berlin: 施普林格科学+商业媒体. 2004. ISBN 3-540-40344-2. Zbl 1058.11070.
The AKS "PRIMES in P" Algorithm Resource（页面存档备份，存于互联网档案馆）
Grime, Dr. James. Fool-Proof Test for Primes - Numberphile (video). 布雷迪·哈蘭. [2018-05-10]. （原始内容于2018-03-23）. [the video describes the exponential time relation (1), which it calls AKS]
一月 30, 2023
aks質數測試, 又被稱為agrawal, kayal, saxena質數測試和cyclotomic, test, 是一個決定型質數測試演算法, 由三個來自印度坎普爾理工學院, 英语, indian, institute, technology, kanpur, 的計算機科學家, 曼寧德拉, 阿格拉瓦爾, 英语, manindra, agrawal, 尼拉吉, 卡亞爾, 英语, neeraj, kayal, 和尼汀, 沙克謝納, 英语, nitin, saxena, 在2002年8月6日發表於一篇題為質數屬於p的論. AKS質數測試 又被稱為Agrawal Kayal Saxena質數測試和Cyclotomic AKS test 是一個決定型質數測試演算法 由三個來自印度坎普爾理工學院 英语 Indian Institute of Technology Kanpur 的計算機科學家 曼寧德拉 阿格拉瓦爾 英语 Manindra Agrawal 尼拉吉 卡亞爾 英语 Neeraj Kayal 和尼汀 沙克謝納 英语 Nitin Saxena 在2002年8月6日發表於一篇題為質數屬於P的論文 1 作者們因此獲得了許多獎項 包含了2006年的哥德爾獎和2006年的富尔克森奖 這個演算法可以在多項式時間之內 決定一個給定整數是質數或者合數 目录 1 重要性 2 概念 3 歷史以及運算時間 4 演算法 4 1 例子 n 31為質數 5 註釋 6 延伸閱讀 7 外部連結重要性 编辑AKS最關鍵的重要性在於它是第一個被發表的一般的 多項式的 確定性的和無仰賴的質數判定算法 先前的算法至多達到了其中三點 但從未達到全部四個 AKS算法可以被用於檢測任何一般的給定數字是否為質數 很多已知的高速判定算法只適用於滿足特定條件的質數 例如 卢卡斯 莱默检验法僅對梅森質數適用 而Pepin測試 英语 Pepin s test 僅對費馬數適用 算法的最長運行時間可以被表為一個目標數字長度的多項式 ECPP和APR能夠判斷一個給定數字是否為質數 但無法對所有輸入給出多項式時間範圍 算法可以確定性地判斷一個給定數字是否為質數 隨機測試演算法 例如米勒 拉宾检验和Baillie PSW 可以在多項式時間內對給定數字進行校驗 但只能給出概率性的結果 AKS算法並未 仰賴 任何未證明猜想 一個反例是确定性米勒检验 該算法可以在多項式時間內對所有輸入給出確定性結果 但其正確性卻基於尚未被證明的廣義黎曼猜想 概念 编辑AKS質數測試主要是基於以下定理 整數n 2 是質數 若且唯若 x a n x n a mod n displaystyle x a n equiv x n a pmod n 1 這個同餘多項式對所有與n互質的整數a均成立 這個定理是費馬小定理的一般化 並且可以簡單的使用二項式定理跟二項式係數的這個特徵 n k 0 mod n displaystyle n choose k equiv 0 pmod n 對任何 0 lt k lt n displaystyle 0 lt k lt n 若且唯若 n 是質數來證明出此定理 雖然說關係式 1 基本上構成了整個質數測試 但是驗證花費的時間卻是指數時間 因此 為了減少計算複雜度 AKS改為使用以下的同餘多項式 x a n x n a mod x r 1 n displaystyle x a n equiv x n a pmod x r 1 n 2 這個多項式與存在多項式f與g 令 x a n x n a x r 1 g n f displaystyle x a n x n a x r 1 g nf 3 意義是等同的 這個同餘式可以在多項式時間之內檢查完畢 這裡我們要注意所有的質數必定滿足此條件式 令g 0則 3 等於 1 因此符合n必定是質數 然而 有一些合數也會滿足這個條件式 有關AKS正確性的證明包含了推導出存在一個夠小的r以及一個夠小的整數集合A 令如果此同餘式對所有A裡面的整數都滿足 則n必定為質數 歷史以及運算時間 编辑在上文引用的論文的第一版本中 作者們證明了算法的漸近時間為O log 12 n displaystyle log 12 n 換言之 算法使用少於n的二進制數字長度的十二次方 但是 論文證明的時間上界卻過於寬鬆 事實上 一個被普遍相信的關於索菲熱爾曼質數分佈的假設如果為真 則會立即將最壞情況減至O log 6 n displaystyle log 6 n 在這一發現後的幾個月中 新的變體陸續出現 Lenstra 2002 Pomerance 2002 Berrizbeitia 2003 Cheng 2003 Bernstein 2003a b Lenstra和Pomerance 2003 並依次提高了算法的速度 以改進幅度為序 由於這些變體的出現 Crandall和Papadopoulos在其科學論文 AKS 類質數測試的實現 2003年三月發表 中將其稱為算法的 AKS 類 出於對這些變體和其他回复的回應 論文 質數屬於P 稍後被進行了更新 新版本包括了一個AKS算法的正規公式化表述和其正確性證明 這一版本在数学年刊上發表 雖然基本思想沒有變化 r displaystyle r 卻被採用了新方法進行選擇 而正確性證明也變得更加緊緻有序 與舊證明依賴於許多不同的方法不同 新版本幾乎只依賴於有限域上的分圓多項式的特徵 新版本同時也優化了時間複雜度的邊界到O log 10 5 n displaystyle log 10 5 n 通過篩法獲得的其他結果可以將其進一步簡化到O log 7 5 n displaystyle log 7 5 n 在2005年 Carl Pomerance和H W Lenstra Jr 展示了一個AKS的變體 可以在O log 6 n displaystyle O log 6 n 次操作內完成測試 n displaystyle n 是被測試數 對於原算法的O log 12 n displaystyle O log 12 n 邊界而言 這是一個顯著的改進 2 演算法 编辑整個演算法的操作如下 1 輸入 整數 n gt 1若存在整數a gt 0 且b gt 1 令 n ab 則輸出合數 找出最小的 r 令 ordr n gt log2 n 若 對某些a r 1 lt gcd a n lt n 輸出合數 gcd是指最大公因數 若 n r 輸出質數 對 a 1 到 f r log n displaystyle scriptstyle lfloor scriptstyle sqrt varphi r log n scriptstyle rfloor 的所有數 如果 X a n Xn a mod Xr 1 n 輸出合數 輸出 質數 這裡的 ordr n 是n mod r的阶 另外 這裡的log 代表以二為底的對數 f r displaystyle scriptstyle varphi r 則是r的歐拉函數 下面說明若n是個質數 那麼算法總是會返回質數 由於n是質數 步驟1和3永遠不會返回合數 步驟5也不會返回合數 因為 2 對所有質數n為真 因此 算法一定會在步驟4或6返回質數 對應地 如果n是合數 那麼算法一定返回合數 如果算法返回質數 那麼則一定是從步驟4或6返回 對於前者 因為n r n必然有因子a r符合1 lt gcd a n lt n 因此會返回合數 剩餘的可能性就是步驟6 在文章 1 中 這種情況被證明不會發生 因為在步驟5中檢驗的多個等式可以確保輸出一定是合數 例子 n 31為質數 编辑 輸入 整數n 31 gt 1 若存在整數a gt 0 且b gt 1 令 n ab 則輸出 合數 for b 2 b lt log2 n b a n1 b If a是整數 輸出 合數 a n1 2 n1 4 5 568 3 141 2 360 計算結果不是整數找出最小的 r 令 ordr n gt log2 n nextR True r 1 while nextR True r nextR False for k 1 nextR amp amp k log2 n k nextR nk r 1 nk r 0 計算結果為 r 29若 對某些a r 1 lt gcd a n lt n 輸出 合數 for a r a gt 1 a If 1 lt gcd a n lt n 輸出 合數 gcd 29 31 1 gcd 28 31 1 gcd 2 31 1 計算結果為找不到符合的a使得1 lt gcd a n lt n為真若 n r 輸出 質數 If n r 輸出 質數 31 gt 29 計算結果n比r大對 a 1 到 f r log n displaystyle scriptstyle lfloor scriptstyle sqrt varphi r log n scriptstyle rfloor 的所有數 如果 X a n Xn a mod Xr 1 n 輸出 合數 for a 1 a f r log n displaystyle scriptstyle lfloor scriptstyle sqrt varphi r log n scriptstyle rfloor a if X a n Xn a Xr 1 n 0 輸出 合數 x a 31 x29 1 31 x a 29 x29 1 31 x a 2 31 x29 1 31 1 a29 29a28x 406 31 a27x2 3654 31 a26x3 23751 31 a25x4 118755 31 a24x5 475020 31 a23x6 1560780 31 a22x7 4292145 31 a21x8 10015005 31 a20x9 20030010 31 a19x10 34597290 31 a18x11 51895935 31 a17x12 67863915 31 a16x13 77558760 31 a15x14 77558760 31 a14x15 67863915 31 a13x16 51895935 31 a12x17 34597290 31 a11x18 20030010 31 a10x19 10015005 31 a9x20 4292145 31 a8x21 1560780 31 a7x22 475020 31 a6x23 118755 31 a5x24 23751 31 a4x25 3654 31 a3x26 406 31 a2x27 29ax28 a2 2ax x2 x29 1 31 1 a29 29a28x 3a27x2 27a26x3 5a25x4 25a24x5 7a23x6 23a22x7 9a21x8 21a20x9 11a19x10 19a18x11 13a17x12 17a16x13 15a15x14 15a14x15 17a13x16 13a12x17 19a11x18 11a10x19 21a9x20 9a8x21 23a7x22 7a6x23 25a5x24 5a4x25 27a3x26 3a2x27 29ax28 a2 2ax x2 x29 1 31 1 2 29 3 31 a2 a31 2 29 31 ax 29 2 1 31 a30x x2 3 2 29 1 31 a29x2 27 2 3 29 31 a28x3 5 2 27 3 31 a27x4 25 2 5 27 31 a26x5 7 2 25 5 31 a25x6 23 2 7 25 31 a24x7 9 2 23 7 31 a23x8 21 2 9 23 31 a22x9 11 2 21 9 31 a21x10 19 2 11 21 31 a20x11 13 2 19 11 31 a19x12 17 2 13 19 31 a18x13 15 2 17 13 31 a17x14 15 2 15 17 31 a16x15 17 2 15 15 31 a15x16 13 2 17 15 31 a14x17 19 2 13 17 31 a13x18 11 2 19 13 31 a12x19 21 2 11 19 31 a11x20 9 2 21 11 31 a10x21 23 2 9 21 31 a9x22 7 2 23 9 31 a8x23 25 2 7 23 31 a7x24 5 2 25 7 31 a6x25 27 2 5 25 31 a5x26 3 2 27 5 31 a4x27 29 2 3 27 31 a3x28 a31 x2 x31 a x29 1 31 a x2 a31 x2 a x2 a31 a f r log 2 n 28 l o g 2 31 26 215 displaystyle sqrt varphi r log 2 n sqrt 28 log 2 31 26 215 131 1 31 0 231 2 31 0 331 3 31 0 2631 26 31 0 計算結果為找不到符合的a使得 X a n Xn a mod Xr 1 n 為真 輸出 質數 31必為質數 註釋 编辑 1 0 1 1 1 2 Manindra Agrawal Neeraj Kayal Nitin Saxena PRIMES is in P 页面存档备份 存于互联网档案馆 Annals of Mathematics 160 2004 no 2 pp 781 793 亨德里克 倫斯特拉 and Carl Pomerance Primality Testing with Gaussian Periods 页面存档备份 存于互联网档案馆 preliminary version July 20 2005 延伸閱讀 编辑Dietzfelbinger Martin Primality testing in polynomial time From randomized algorithms to PRIMES is in P Lecture Notes in Computer Science 3000 Berlin 施普林格科学 商业媒体 2004 ISBN 3 540 40344 2 Zbl 1058 11070 外部連結 编辑埃里克 韦斯坦因 AKS Primality Test MathWorld R Crandall Apple ACG and J Papadopoulos March 18 2003 On the implementation of AKS class primality tests PDF Article by Borneman containing photos and information about the three Indian scientists 页面存档备份 存于互联网档案馆 PDF Andrew Granville It is easy to determine whether a given integer is prime 页面存档备份 存于互联网档案馆 The Prime Facts From Euclid to AKS 页面存档备份 存于互联网档案馆 by Scott Aaronson PDF The PRIMES is in P little FAQ 页面存档备份 存于互联网档案馆 by Anton Stiglic 2006 Godel Prize Citation 2006 Fulkerson Prize Citation 页面存档备份 存于互联网档案馆 The AKS PRIMES in P Algorithm Resource 页面存档备份 存于互联网档案馆 Grime Dr James Fool Proof Test for Primes Numberphile video 布雷迪 哈蘭 2018 05 10 原始内容存档于2018 03 23 the video describes the exponential time relation 1 which it calls AKS 取自 https zh wikipedia org w index php title AKS質數測試 amp oldid 74336762, 维基百科，wiki，书籍，书籍，图书馆，
