フェルマーテスト
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 22:35 UTC 版)
「フェルマーの小定理」の記事における「フェルマーテスト」の解説
フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。 フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。 対偶 n と互いに素な整数 a が a n − 1 ≢ 1 ( mod n ) {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}} を満たせば、n は合成数である。 この十分条件を用いて、次のように自然数 n の素数判定を行う。 パラメータとして、2 以上 n 未満の自然数 a を1つ定める。 a と n が互いに素でなければ「n は合成数」と出力して終了。 a n − 1 ≢ 1 ( mod n ) {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}} ならば「n は合成数」と出力して終了する。そうでないとき「n は確率的素数」と出力して終了する。 フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。 疑わしければ、「確率的素数」と出力された場合にはまた異なる a を用いて再びテストを行う。十分な回数だけ a を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。 しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにもかかわらず、ほとんどいかなる a を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。 フェルマーテストを改善するアルゴリズムとしては、ミラー–ラビン素数判定法やAKS素数判定法がある。
※この「フェルマーテスト」の解説は、「フェルマーの小定理」の解説の一部です。
「フェルマーテスト」を含む「フェルマーの小定理」の記事については、「フェルマーの小定理」の概要を参照ください。
- フェルマーテストのページへのリンク
