確率的素数判定法 - ﾕﾕﾕﾕﾕ

ある自然数 n が素数であるかどうかを決定論的に調べるには、少なくとも $\sqrt{n}$ まで調べないといけない。

しかし確率論的に素数である可能性が高いということであれば、 $O(log_{} n)$ で計算することができる。これは速度と確度のトレードオフというわけでなく、確率論的な判定で実用上は問題ないということをいっている。

$a$ を $n$ より小さい自然数とする。このとき

$n は素数 \Rightarrow a^{n} \equiv a \mod n$

が成り立つ。

対偶はもちろん

$a^{n} \not\equiv a \mod n \Rightarrow n は素数でない$

になる。

$a^{n} \equiv a \mod n \Rightarrow n は素数$

は必ずしも成り立たない。あくまで $n$ が素数である可能性があるということしか言えない。

しかしここで、 $n$ より小さい $a$ を繰り返し選んで、いずれの $a$ も $n$ が素数である可能性を示唆するのであれば、 $n$ が素数である可能性がより高いとすることができる。

この発想に基づくアルゴリズムをフェルマーテストという。

フェルマーテストを出し抜く数、つまり実際には素数でないのに、素数である可能性が高いと判定される数列がある。

これをカーマイケル数という。10⁸ 未満のカーマイケル数は 255 個存在し、 $561, 1105, 1729, 2465, 2821, 6601, ...$ と続く。

数がより大きくなるにつれてカーマイケル数はより希少になっていき、フェルマーテストが欺かれるリスクもそれだけ減少していく。 SICP はこれを、「宇宙線の影響でアルゴリズムが誤動作するよりも低い可能性」と説明している。

つまり、カーマイケル数の存在をもってアルゴリズムを非実用的とするのであれば、この宇宙でコンピューターを動作させることも同様に非実用的となる。それはマヌケな話であるので、カーマイケル数の存在にも関わらずフェルマーテストは有効に用いられている。

その代表選手が RSA 暗号である。

フェルマーテストが実用的にじゅうぶん有用であるいっぽうで、フェルマーテストを改良した形でカーマイケル数にも対応したアルゴリズムがある。それがミラー-ラビンテストと呼ばれるものである。

これは aⁿ を計算する過程で平方数を求めるたびごとに、

を満たすような x があらわれないことを確かめる手続きを含むものである。このような x が出現するとき、 n は素数でないことを証明することができる（しかしこれは僕の手には余った）。

scheme で実装するとこうなる。これも独力では実装が叶わず、以下のリンクを参考に作った。