素数判定（そすうはんてい、）とは、与えられた自然数が素数か合成数かを分ける事。素数判定を行う算法を素数判定法という。
RSA暗号の鍵生成上重要なので、計算理論、特に暗号学上で高速な素数判定が研究されている。
種類 試し割り法が代表的で、プログラムのデモによく登場する。実装が簡易な手法として、アトキンの篩やフェルマーテストがある。
実用上はミラーラビン法やBaillie–PSW primality testが高速だが、決定的判定法としてECPPも併用する。
2の冪やその自然数倍に対しては、数論から次数の低い多項式時間で動く算法が知られている。特にメルセンヌ数を判定するリュカ法は、2021年までGIMPSに採用されていた。
詳細 一般 決定的素数判定法 試し割り法 エラトステネスの篩、アトキンの篩、サンダラムの篩 最大公約数 ウィルソンの定理 Millerテスト - 多項式時間アルゴリズムだが、一般化されたリーマン予想(GRH)のもとで正当性が示される。 - 高速だが、多項式時間アルゴリズムではない。 （楕円曲線素数判定法） AKS素数判定法 - 多項式時間アルゴリズム 確率的素数判定法 フェルマーテスト ソロベイ–シュトラッセンテスト ミラー–ラビン素数判定法
或る条件の数に対する判定法 - , Fの素因数分解が既知の場合の判定法 リュカ・テスト - が型素数のメルセンヌ数に対する判定法 リュカ–レーマー・テスト - が奇素数のメルセンヌ数に対する判定法 リュカ–レーマー–リーゼル・テスト より特殊な数を対象とする算法 - プロス数に対する判定法 - フェルマー数に対する判定法
確率的素数判定法 素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 n の合成数性のみを調べる判定法がある。この判定法を確率的素数判定法 (probabilistic 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に属することが判明した。1992年にはAdleman-HuangによるアルゴリズムがZPP = RP ∩ co-RPまで複雑性を下げ、Prattによる結果を更新した。
1983年に発見されたAdleman–Pomerance–Rumelyによる素数判定法によりPRIMESはQPに属することが判明したが、これと上記の結果との関係は分かっていない。
その実際上の扱いやすさや、リーマン予想に基づく多項式時間アルゴリズムの存在、その他の類似の状況証拠により、素数判定は多項式時間でおこなえると長く信じられてきたが、証明はできなかった仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上は等がより速い。
AKS素数判定法が最終的にこの長年の問題に終止符を打ち、PRIMESがPに属することを証明した。しかしながら、PRIMESがP-完全かどうかは分かっておらず、NCやLなどのPに含まれるクラスに属するかどうかも分かっていない。PRIMESがAC0に属しないことが証明されている。E. Allender, M. Saks, and I.E. Shparlinski, A lower bound for primality, J. Comp. Syst. Sci. 62 (2001), pp. 356–366.
プログラム例 Pythonによる素数判定（試し割り法）のプログラム例を示す。 import math
def is_prime(n): if n <= 1: return False
if n == 2: return True
if n % 2 == 0: return False
for i in range(3, math.ceil(math.sqrt(n)) + 1, 2): if n % i == 0: return False
return True この例は入力nが素数である場合はTrueを返し、それ以外の場合はFalseを返す。
Pythonによる素数判定(エラトステネスの篩)のプログラム例を示す。 import math
def eratosthenes(n): list_prime = list(range(2, n))
for i in range(2, n): if i in list_prime: for j in range(i * 2, n, i): if j in list_prime: list_prime.remove(j)
if i > int(math.sqrt(n)): break
return list_prime この例は入力nまでの素数のリストを返す。
外部リンク https://asanobuturi.github.io/document/2018/14/
脚注
注釈
出典