この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "素数判定"
素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。
RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。
仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はAPR判定法（英語版）などのほうが高速であることが多い。
なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。 素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 n を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を確率的素数判定法 (probabilistic primality test) ということがある。これに対して「素数である」あるいは否と判定する決定的アルゴリズムは決定的素数判定法 (deterministic primality test) ということがある。 「合成数である」と判定した場合には、nは合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。しかし、判定を適当な回数だけ繰り返し、その間一度も「合成数である」と出力されないならば、その n は素数である見込みが大きいと言える。このようにして得られた「素数ではないかと思われる数」のことを確率的素数 (probable prime) という。 一般に確率的素数判定法は、決定的素数判定法よりもはるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。 また、ミラー?ラビン素数判定法はある種の一般化されたリーマン予想のもとでは多項式時間で動く素数判定法として動作することが知られている。 計算複雑性理論では、ある数が素数かどうかを判定する問題はPRIMESと表記される。PRIMESがco-NPであることは簡単に示すことができる。なぜなら、その補問題であるCOMPOSITE（ある数が合成数であるかどうかを判定する問題）は、任意の数に対し、問題の数がそれで割り切れるかどうかの確認が多項式時間で行えることよりNPに属するからである。 1975年にVaughan PrattはPRIMESがNPに、また従ってNP ∩ co-NPに属することを示した（Primality certificate Solovay-StrassenとMiller-RabinによるアルゴリズムによりPRIMESはco-RP
確率的素数判定法
計算複雑性
1983年に発見されたAdleman?Pomerance?Rumelyによる素数判定法によりPRIMESはQPに属することが判明したが、これと上記の結果との関係は分かっていない。
その実際上の扱いやすさや、リーマン予想に基づく多項式時間アルゴリズムの存在、その他の類似の状況証拠により、素数判定は多項式時間でおこなえると長く信じられてきたが、証明はできなかった。AKS素数判定法が最終的にこの長年の問題に終止符を打ち、PRIMESがPに属することを証明した。しかしながら、PRIMESがP-完全かどうかは分かっておらず、NCやLなどのPに含まれるクラスに属するかどうかも分かっていない。PRIMESがAC0に属しないことが証明されている。[2]
様々な判定法