AKS素数判定法

AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 <math>n</math> が素数であるかどうかを判定するのにかかる時間が<math>\\log(n)</math> の多項式を上界とすることをいう。<math>n</math> の多項式ではないことに注意する必要がある。AKS素数判定法は2002年8月6日に \"PRIMES is in P\" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。