確率的素数判定法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/01 09:24 UTC 版)
素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 n を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を確率的素数判定法 (probabilistic primality test) ということがある。これに対して「素数である」あるいは否と判定する決定的アルゴリズムは決定的素数判定法 (deterministic primality test) ということがある。 「合成数である」と判定した場合には、nは合成数であると確定するが、「良く分からない」と判断した場合には、それだけではあまり有用な情報は得られない。しかし、判定を適当な回数だけ繰り返し、その間一度も「合成数である」と出力されないならば、その n は素数である見込みが大きいと言える。このようにして得られた「素数ではないかと思われる数」のことを確率的素数 (probable prime) という。 一般に確率的素数判定法は、決定的素数判定法よりもはるかに高速であるので、実用上は確率的素数判定法の繰り返しをもって素数判定法に代える場合も多い。 また、ミラー–ラビン素数判定法はある種の一般化されたリーマン予想のもとでは多項式時間で動く素数判定法として動作することが知られている。
※この「確率的素数判定法」の解説は、「素数判定」の解説の一部です。
「確率的素数判定法」を含む「素数判定」の記事については、「素数判定」の概要を参照ください。
ウィキペディア小見出し辞書の「確率的素数判定法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 確率的素数判定法のページへのリンク
