AKS質數測試
維基百科,自由的 encyclopedia
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年的富尔克森奖。這個演算法可以在多項式時間之內,決定一個給定整數是質數或者合數。