素数マスターへの道(6)

ちょい脱線

前回、

水さすようで申し訳ないんですが、フェルマーテストはカーマイケル数に対して高確率で false positiveになります。
ミラー・ラビン素数判定は一つの底で判定する度に1/4の確率でしか素数性を担保出来ません。
確実な素数判定となるとAKS素数判定法を使うかエラトステネスの篩で求めるか、検査する数をnとするとn^(1/2)までの数で検算するなどしないと駄目だったはずです。

というid:rayfillさんのコメントがあったので、ちょっと本題から外れて解説をしておきます。

カーマイケル数がなんちゃら

フェルマーテストではどんな基数を用いても特定の合成数を擬素数と判定してしまう場合があります。そのような数をカーマイケル数と言いますので、“高確率”ではなく“必ず”そうなります。

ミラー・ラビンがなんちゃら

数論の本とかネットをさららっと眺めていると、「75%」とか「1/4」みたいな数字をよく目にしますが、これは100個のうち75%しか正しく判定できないとか、1/4の確率で素数と判断できるという意味ではありません。

ある奇数nについて、ミラー・ラビンテストを行う場合、nが合成数であると正しく判別できる基数a(nに対する証人)は、1〜n-1の中に少なくとも75%はあるよ！という意味であって、N個の奇数群に対して基数aでテストを行った場合75%の確率でうまくいくヨ！ということとは全く違います。

そもそも、フェルマーテストやミラー・ラビンテストというのは、素数性ではなく非素数性を調べるためのものなので、1/4とかいう数字を持ち出すと誤解をしやすくなります。「1/4」は、「ある数nに対して1〜n-1の中から任意に選んだ値でのミラー・ラビンテストにおいて、“非”素数性の判定に“最大”1/4の確率で失敗する」という文脈での「1/4」であり、素数性云々に使える数値ではありません。

試し割とかAKS素数判定法じゃないとダメなのか

ロベールさんのコメントを引用しますと

ミラーラビンでも、拡張リーマン予想が正しいと仮定すれば
確実な素数判定のできる方法も存在します。
拡張リーマン予想は未解決問題ですけど、
実際に使ってみてもちゃんと素数判定できてるので、大丈夫そうな感じです。
（むしろできなかったら拡張リーマン予想の反証という歴史に残る大発見になるレベル）
問題の値域に限定するならば、2, 7, 61 のたった３つの底で判定するだけでも擬素数は現れなくなります。

とのことです。
証明されていないことを前提としているので100%YESとは言えない。だからこそ『確率的アルゴリズム』という位置に止まっていますが、『拡張リーマン予想の反証』がなされない限り、現実的には限りなく100%に近いYESと言えるのではないでしょうか。

で、実際の割合は

ミラー・ラビンテストを行うとき、実際のところ、nに対する証人が75%〜80%くらいのnというのは、奇数全体に対してごくわずかです。ほとんどの奇数においては95%を超えています。例えば1〜100000までの奇数について、証人の数が80%切るような値は、9, 703, 1891, 12403, 38503, 79003, 88831の7つしかありません。

n	nに対する証人
9	75.00%
703	76.92%
1891	76.19%
12403	75.47%
38503	75.27%
79003	75.19%
88831	75.18%

ちなみに、1〜100000までのカーマイケル数は、561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361の16個しかありませんから、ミラー・ラビンテストよりも精度の低いフェルマーテストを使用しても、大きなロスにはなりません。

それから、ある“奇数”に対して任意の“基数”を用いてミラー･ラビンテストを行った場合、合成数を擬素数と判定してしまう確率は、非常に低い思われます。
1から数えて100万個の奇数において、各奇数毎に500程度の基数を用いてミラー・ラビンテストを行いましたが、どの基数の場合もほとんどが0.01%前後になりました。大きくても0.05%程度です。ミラー・ラビンテストはかなり優秀ですね。

素数判定の目的

ある数が素数かどうかを判定する必要があるとき、“確実性が求められるかどうか”によって、計算手法は異なります。

素数性を前提とした暗号化技術を使おうと思えば、常に間違いなく素数であるといえる値を用意する必要があります。研究としての素数判定であれば、確実性について明確な前提を用意しなければならないでしょう。

暗号化技術に必要とは言っても、それは“暗号化を行う側”にとって重要な話しで、暗号を破ってやろうというクラッカーにとっては確実性なんてどうでも良い話で、むしろ不確実な部分を突くのが仕事です。

今回題材としているPrime Checkerという問題は、判定する値の集合は予め知られていて、その大きさも1〜2^31までの間であることがわかっています。そういう場合は大雑把な判定を行い、例外的な部分は個別に対応すれば済むわけです。

仮に確実性が必要だとしても、大量の値について素数判定するならば、ミラー・ラビンテストによって合成数(非素数性)を実用的な速度で発見し、篩い落とす作業は重要でしょう。

つづく