概要

フェルマーの素数判定法は、整数 n が素数である可能性が高いかどうかを調べる簡単な確率的手法です。フェルマーの小定理に基づいており、p が素数で a が 1<a<p を満たす任意の整数なら、a^(p-1) ≡ 1 (mod p) となります。この判定法では 1 つ以上の底 a を選び、合同式が成り立つかを確かめます。失敗すれば n は合成数であると証明され、成功すれば n は素数候補になります。

判定のしくみ

基本的な手順は単純で、実装もしやすいものです。選んだ底 a（1<a<n）について:

  • 高速なべき剰余計算を使って a^(n-1) mod n を求める。
  • 結果が 1 でなければ、n は合成数。
  • 結果が 1 なら、n は底 a に対する素数候補（フェルマー素数候補）である。

異なる底で繰り返し試すことで、合成数が偶然通過する確率を下げられます。多くの実装では、信頼度を高めるために複数の乱数底または選択した底を用います。アルゴリズムの詳細は アルゴリズムの詳しい説明 も参照してください。

限界と擬素数

フェルマーの判定法は高速ですが、完全ではありません。一部の合成数は、n と互いに素な多くの a、あるいはすべての a に対して a^(n-1) ≡ 1 (mod n) を満たします。こうした数はカーマイケル数と呼ばれ、判定法をだまして合成数を素数候補と表示させることがあります。特定の底 a に対してこの判定を通過する数は、その底に関するフェルマー擬素数と呼ばれます。関連する内容として カーマイケル数 なども参照してください。

歴史と実用上の使い道

この判定法はフェルマーの小定理に関する考え方に由来し、初期の計算数論では素数判定の迅速なふるい分けとして用いられてきました。今でも、非常に速く低コストな確認が必要な場面、たとえばより強力な判定を適用する前の予備段階として有用です。ただし、偽陽性があるため暗号鍵生成に単独で使うことは推奨されず、ミラー–ラビン法の強擬素数判定のような、より強力な確率的判定や決定的手法が好まれます。さらに詳しい資料や比較は 詳細な参考資料 で確認できます。

注目すべき点: この判定法は、べき剰余計算を多項式時間で行えるため実用上とても高速です。単純さゆえに、教育用の道具としても、より堅牢な素数アルゴリズムへの橋渡しとしても役立ちます。