1 基本概念
素数判定は、整数が1とその数自身以外に約数をもたないかを調べる手続きである。対象が素数ならその性質に応じた数論的処理へ進み、合成数なら因数構造の確認や分解計算へ移る。数学では純粋な性質の確認として、計算機科学では処理速度や資源消費の観点から扱われる。
1.1 素数と合成数
素数は、2以上の整数で、約数が1と自分自身に限られる数をいう。合成数はそれ以外の2以上の整数で、必ず非自明な約数をもつ。なお1はどちらにも分類されず、素数判定では通常、別扱いとなる。
1.2 素数判定の目的
この判定の目的は、数の構造を把握することにある。たとえば暗号計算では大きな素数が必要となり、数表の生成では素数の列挙が重要になる。理論研究では、素数の分布や計算可能性を調べる基礎にもなる。
1.3 判定問題としての位置づけ
素数判定は、入力された整数がある性質を満たすかを答える判定問題の一種である。一般には「はい」「いいえ」で返答できるため、アルゴリズムの計算量を比較しやすい。単純そうに見えるが、巨大整数に対しては計算効率が大きな論点となる。
2 初等的な判定法
初等的な方法は、原理がわかりやすく、少ない理論知識で実装できる点に特徴がある。小さな数には十分有効であり、他の高速法の前処理として使われることも多い。
2.1 試し割り法
試し割り法は、候補となる約数で順に割っていく最も基本的な手法である。割り切れれば合成数、最後まで割れなければ素数と判断する。簡潔だが、大きな数では試行回数が増えやすい。
2.1.1 割り切れ判定
ある整数が別の整数でちょうど割れるかを確認する方法である。余りが0ならその約数をもつため、素数ではない。最初の段階で2や3のような小さな因子を調べると、不要な計算を減らせる。
2.1.2 平方根までの確認
合成数には平方根以下の約数が必ず存在するため、判定は√nまで調べれば足りる。これにより、全ての候補を確認するよりも計算量を抑えられる。実用上は、奇数だけを調べるなどの簡略化も行われる。
2.2 ふるいを用いる方法
ふるいは、複数の整数をまとめて扱う場合に向いた方法である。ある範囲の数から合成数を除外していくため、素数一覧の作成に適している。単発の判定よりも、範囲全体の探索で威力を発揮する。
2.2.1 エラトステネスのふるい
小さい素数から順に、その倍数を消していく古典的手法である。最後まで残った数が素数として得られる。実装が容易で、教育用の例としても広く用いられる。
2.2.2 節約されたふるい
メモリ使用量や処理時間を減らすために、記録方法を工夫したふるいである。奇数だけを対象にしたり、区間ごとに分けて処理したりする。大規模な範囲を扱う際に有効で、実務では標準的な改良として知られる。
2.3 素因数分解との関係
素数判定と素因数分解は密接に結びついている。ある数が素数でなければ、因数の探索が次の課題になるためである。ただし、分解が難しいからといって判定も同程度に難しいとは限らず、計算上は別個の問題として扱われる。
3 高速な判定法
高速な判定法は、大きな整数を短時間で扱うために考案された。多くは指数法則や合同式を利用し、必要な確認回数を減らす。なかには確率的な判定を含み、誤判定の可能性を極小化する設計が取られる。
3.1 フェルマーテスト
フェルマーテストは、フェルマーの小定理を利用して素数らしさを調べる方法である。計算が軽く、初期のふるい分けに向く一方、例外的な合成数に弱い。
3.1.1 フェルマーの小定理
pが素数で、aがpと互いに素なら、a^(p-1) は p で割ると1余る。これを逆向きに用い、与えられた数に対して同様の関係が成り立つか確認する。合同式を使うため、巨大な指数でも比較的処理しやすい。
3.1.2 偽陽性の問題
合成数でありながら、定理に似た振る舞いを示してしまう数がある。これにより、フェルマーテストだけでは確定判断にならない場合がある。したがって、単独使用よりも他の方法との併用が望ましい。
3.2 ミラー・ラビン判定法
ミラー・ラビン判定法は、広く使われる確率的素数判定である。複数の基底で検査すると、合成数を誤って素数とみなす確率を急速に下げられる。実用面での信頼性が高く、実装例も多い。
3.2.1 強擬素数
ある基底に対して、合成数なのに素数のような挙動を示す数を強擬素数という。ミラー・ラビン法では、この種の例外を見つけるために段階的な検査を行う。基底を変えることで、誤りの入り込みを大きく抑制できる。
3.2.2 確率的性質
この方法の誤判定率は、反復回数を増やすほど低下する。適切な乱数基底を選べば、実用上ほぼ確実な判定が可能になる。計算速度と信頼性の均衡が良く、暗号用途でも重要な位置を占める。
3.3 ソロベイ・シュトラッセン判定法
ソロベイ・シュトラッセン法は、オイラーの判定基準に基づく確率的手法である。ミラー・ラビン法ほど一般的ではないが、理論的に興味深い性質をもつ。合同算術の構造を直接反映する点が特徴である。
3.3.1 オイラーの判定基準
オイラーの基準は、素数に対して成立する特定の合同関係を利用する。これを逆用して、入力値がその性質を示すかどうかを確かめる。平方剰余の考え方と結びついている。
3.3.2 実用上の特徴
理論的には整った方法だが、実務ではより効率のよい手法が選ばれることが多い。計算の安定性や誤判定率の扱いで、ミラー・ラビン法に比べて優先度が下がる場合がある。それでも数論教育では有用な例となる。
4 決定的判定法と理論的発展
決定的判定法は、確率に頼らず正確な結論を返すことを目指す。長く難問とされたが、理論の進展により多項式時間での判定可能性が示された。これは計算複雑性理論にも重要な影響を与えた。
4.1 決定的多項式時間判定
決定的多項式時間とは、入力の大きさに対して計算量が多項式で抑えられることを意味する。素数判定がこの枠内に入ることは、理論上の大きな節目であった。実際の高速性と、数学的保証の両面で意義がある。
4.1.1 判定可能性の理論
ある問題が効率よく解けるかどうかは、計算量クラスの議論と関わる。素数判定は、直感に反して低い計算複雑性をもつことが示された。これにより、数論問題と理論計算機科学の接点が強まった。
4.1.2 ＡＫＳ素数判定法
ＡＫＳ素数判定法は、条件を満たすかを決定的にチェックする有名なアルゴリズムである。理論的には画期的だが、実装面では確率的法に比べて遅いこともある。それでも、素数判定が多項式時間で可能であることの証拠として重要である。
4.2 楕円曲線を用いる手法
楕円曲線を利用した方法は、特定の条件を満たす素数の証明や検査に役立つ。通常の判定だけでなく、証明書を伴う形で使われることがある。これは巨大な数に対する信頼性の高い評価に向く。
4.2.1 楕円曲線の性質
楕円曲線は、代数的な方程式で表される幾何学的対象である。その群構造が数論的検証に応用される。点の個数や演算の性質が、素数性に関する情報を与える。
4.2.2 証明可能素数判定
判定結果に加えて、その正しさを第三者が確認できる形式を重視する方法である。証明付きの素数性評価は、記録や検証の場面で有用である。大きな数に対しても、検証側の負担を抑えられる。
4.3 理論計算量との関係
素数判定は、実際には速いだけでなく、理論上どの程度の資源で処理できるかが問われる。多項式時間の達成は、アルゴリズム理論の成果として位置づけられる。さらに、確率的計算と決定的計算の比較にも関係する。
5 実用上の考慮事項
実際の利用では、数学的な正しさだけでなく、入力サイズ、計算機資源、実装の容易さが問題になる。用途に応じて方法を選ぶことが、性能と信頼性の両立につながる。
5.1 大きな整数への対応
大きな整数では、通常の機械語だけでは扱いきれないため、多倍長整数演算が必要になる。演算コストが増すので、判定法自体の効率に加え、基礎演算の最適化も重要である。これにより、実用可能な範囲が大きく広がる。
5.2 乱数の利用
確率的判定では、基底選択に乱数を使うことが多い。適切な乱数源は、偏りの少ない検査を支える。安全性を重視する場面では、乱数の品質そのものも評価対象になる。
5.3 実装上の最適化
実装では、理論的に同じ手法でも定数倍の差が大きな影響を及ぼす。不要な剰余計算を避け、データ表現を工夫することで速度が向上する。アルゴリズム設計と低レベル最適化の両方が関与する。
5.3.1 乗算高速化
多倍長整数の乗算を速くすることは、素数判定全体の性能に直結する。桁数が増えると通常の乗算は重くなるため、より効率的な方法が採用される。これにより、大きな入力でも処理時間を抑えやすい。
5.3.2 冪剰余計算
合同式のもとでべき乗を効率よく求める計算である。二分累乗法のような技法を使えば、巨大な指数でも短い手順で済む。多くの高速判定法の中心的な計算要素となっている。
5.4 用途別の使い分け
小さい数の一括処理ならふるい、大きな単発判定なら確率的手法や決定的法が選ばれやすい。証明の要否、実行速度、実装の複雑さによって最適解は変わる。現場では、複数の方法を段階的に組み合わせることも一般的である。
6 関連する数論的概念
素数判定は、周辺の数論概念と密接につながる。相互に関連する性質を理解すると、判定法の意味や適用範囲が見えやすくなる。
6.1 互いに素
2つの整数が共通の約数1しかもたないとき、それらは互いに素という。多くの判定法では、この条件が成立するかどうかが前提になる。最大公約数の計算は、その確認に使われる。
6.2 オイラー関数
オイラー関数は、ある整数以下でそれと互いに素な数の個数を表す。素数やその冪に対して明快な式をもつため、数論的性質の整理に役立つ。判定法の証明や関連定理にも頻繁に現れる。
6.3 原始根
法pのもとで、ある元のべき乗がすべての非零剰余類を生成する場合、その元を原始根という。素数の剰余構造を理解するうえで重要である。合同式を用いる検査法との親和性も高い。
6.4 整数分解アルゴリズムとの連携
素数判定と整数分解は別問題だが、実際には連携して用いられる。合成数と分かれば分解へ進み、逆に因数が見つかれば素数性は否定される。総合的な数論計算では、両者を組み合わせて効率を高める。