素数判定
素数判定(そすうはんてい、英: primality test)とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。
RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。
仮定なしで決定的かつ多項式時間で終了する(クラスPに含まれる)素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された(AKS素数判定法)。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はAPR判定法(英語版)などのほうが高速であることが多い。
なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。
計算複雑性理論では、ある数が素数かどうかを判定する問題はPRIMESと表記される。PRIMESがco-NPであることは簡単に示すことができる。なぜなら、その補問題であるCOMPOSITE(ある数が合成数であるかどうかを判定する問題)は、任意の数に対し、問題の数がそれで割り切れるかどうかの確認が多項式時間で行えることよりNPに属するからである。
1975年にVaughan PrattはPRIMESがNPに、また従ってNP ∩ co-NPに属することを示した(Primality certificateを参照)。
Solovay-StrassenとMiller-RabinによるアルゴリズムによりPRIMESはco-RPに属することが判明した。1992年にはAdleman-HuangによるアルゴリズムがZPP = RP ∩ co-RPまで複雑性を下げ、Prattによる結果を更新した。
1983年に発見されたAdleman–Pomerance–Rumelyによる素数判定法によりPRIMESはQPに属することが判明したが、これと上記の結果との関係は分かっていない。
その実際上の扱いやすさや、リーマン予想に基づく多項式時間アルゴリズムの存在、その他の類似の状況証拠により、素数判定は多項式時間でおこなえると長く信じられてきたが、証明はできなかった。AKS素数判定法が最終的にこの長年の問題に終止符を打ち、PRIMESがPに属することを証明した。しかしながら、PRIMESがP-完全かどうかは分かっておらず、NCやLなどのPに含まれるクラスに属するかどうかも分かっていない。PRIMESがACに属しないことが証明されている。