確率的素数：確率的素数判定法の種類、信頼性と暗号での用途

一般的な判定法と分類

異なる判定法により、異なる種類の確率的素数が定義される。代表例には次がある。

• フェルマー確率的素数：選んだ底 a に対し、n が a^(n-1) ≡ 1 (mod n) を満たす数。これはフェルマーの小定理に基づく。フェルマー判定法を参照。
• オイラー確率的素数およびオイラー＝ヤコビ確率的素数：二次剰余を用いて偽陽性を減らす改良法である。
• 強確率的素数（しばしばミラー＝ラビン判定法による）：無作為に選んだ底ごとの誤りの確率がはるかに小さい、より厳格な検査である。
• リュカ確率的素数とその変種：漸化数列と代数的性質に基づく判定法である。

信頼性と誤り

確率的判定法は、合成数が無作為に選ばれたパラメータに対して高い確率で不合格となるよう設計されている。最も広く用いられる強確率的素数判定法であるミラー＝ラビン判定法では、奇数の合成数が強確率的素数となる底は、可能な底のうち高々一定の割合に限られる。これにより、1回の判定あたりの誤りに具体的な上限が与えられる。独立した複数の底で判定を繰り返せば、合成数を誤って受理する確率は、実用上無視できる水準まで下げられる。

歴史と発展

確率的素数判定法は、フェルマーの小定理から得られる単純な帰結を出発点として、群や体の構造を利用する、より洗練されたアルゴリズムへと発展した。20世紀に改良され、現在でも多くの用途において大きな数の素数性を確認する最速の方法であり続けている。素数判定には決定論的多項式時間アルゴリズムも存在するが、実際の利用では、確率的判定を繰り返す方法より通常は遅い。

用途と例

暗号では、鍵に用いる大きな素数を生成するため、確率的素数判定法が日常的に使われる。無作為な奇数の候補を複数の底での判定に合格するまで検査し、十分に高い確信をもって素数として受理する。よく知られた合成数はその限界も示している。341（11×31）は底2に関するフェルマー擬素数であり、カーマイケル数は、それと互いに素なすべての底についてフェルマー判定に合格する合成数である。そのため実務家はミラー＝ラビンのようなより強い判定法を好み、ミラー＝ラビンの変種や、証明可能なアルゴリズムなど、決定論的方法または証明書を生成する方法で追加の確認を行うことがある。

区別と重要な事実

「確率的素数」は素数性の証明ではない。厳密な保証には、素数性証明書または決定論的アルゴリズムを用いる。それでも、速度と極めて低い誤り確率の均衡により、確率的素数判定は計算機科学と暗号における大きな数の素数性判定の実用的な標準となっている。