腹が立つので底を3に変えて化けの皮をはがしてやろう。3442.底を3に変えるとフェルマーの(弱い)擬素数にすらならないことが分かる(最後の項まで来ても≡1にならない)。複数の底に対して擬素数でありつづけることは非常に難しいのだ。この記事では分かりやすくベタでリストを書いたが、実際には大きな指数計算を何度もする必要ない。「前の項の二乗」の剰余は、「前の項の剰余の二乗」の剰余に等しいので、次のように計算量を大幅に節約できる。);</script>実装上、最初の項で1になれば、その段階で合格となり、以下続けても結論は変わらないので、ただちに中止して良い。ない場合、-1が出ればその段階で合格となり、以下続けても結論は変わらないので、そこで中止して良い。最後の項のひとつ手前まで来ても-1にならないなら、その段階で不合格である。どっちにしても最後の項は実際に計算する必要ない。理論上、途中で1が出てその前の項が≡±1でなかったなら、本物の素数でないと判断できるので、そこで中止できる。実装上、1が出た瞬間にやめても計算量を極端に減らせるわけではない。異なる底に対してミラーのテストを反復することを、一般にラビン・ミラー(Rabin-Miller)のテストという。したがって、理論的には、ラビン・ミラーテストにより「素数性品質」を定量的に管理できる。0.00098となる。理論上、フェルマーテストの場合、すべての有効な底に対してどれでやっても擬素数になる可能性が極めてわずかながらある。ミラーテストを使った巨大な整数の素数性判定では、底の数を増やせば失敗確率を望むだけ小さくできる。d305242003年に書かれた記事です。上で構築する道筋を示しています。2004年には、ずっと強い1024ビットのRSAを、もっと効率的に実装できるようになりました。分かりやすいかもしれません。この古い記事も、参考として残しておきます。以下、古い記事JavaScript上で、1分程度で20~40桁の素数を見つける確率的アルゴリズムを実装し、計算の複雑性理論についていくつかの実感をつかむ。少なくとも128~160ビットの鍵を生成できる。100ビットのRSA暗号をJavaScript上に構成できた。64ビットについてはJavaScriptだけで完全なアプリケーション・インターフェイスを構築することさえできた。足し算、掛け算といったところから自前で準備しなければならない。ふるいの方法の計算時間は、桁数についての多項式では済まず、指数時間だ。8桁長くなると1万倍......という途方もない勢いなので、100ビットがぎりぎりという状況では、104ビットや108ビットというわずかな前進も、もはや困難である。(ぎりぎり待てる限度の100倍や1万倍の時間は待てない。してそうなるかと言えば、桁数が2桁伸びるごとにふるいでは割り算の数が明らかに約10倍になるからだ。したがって、2003年現在、先に進むには通常、確率的アルゴリズムを使う。現実によく使われるのはフェルマーテストまたはその強化版だ。ミラーテストと強擬素数で準備した内容を実装すればよい。N)を満たすかどうか確かめれば良い。これを満たさないなら絶対に素数でないので、実際に因数を知ることなく、合成数であると断定できる。Cについて「AをB乗してCで割った余りを求める」Bigint.powmod()がすでに入っているので、速度はイマイチだが、上記のことはほんの数行の手間だ。;}これがfalseを返すものは確実に合成数であるから捨てる。trueが返った場合は「たぶん」素数だ。教科書を読んでも得られないようななまなましい実感が体得できるだろう。JavaScriptの実演なので、もちろんJavaScriptが有効なブラウンジング環境が必要。CPUに負荷がかかるので注意。ふるいにかけてから、フェルマーテストまずページを開くと「素数を探します。数分かかる可能性があります。」というダイアログが出る。これは間違えて起動してしまったときにキャンセルするためのもので、たいした意味はない。ここで「第一の素数を探しています...」と表示されて確率的な探索が始まる。このデモでは20桁の乱数を発生させて、ミラーとラビンによる反復的・強化版フェルマーテストを行う。その前段階として、エラトステネスのふるいを軽くかけて、10000以下の素数で割れるものは飛ばす。(13)...のようなデバッグメッセージが出るのは、[]内の20桁の数が()の小さい素数で割れてしまって予選落ちしたことを意味する。この点には深い意味はない。意図としては単にデバッグメッセージがごちゃごちゃしすぎないように、そうしているにすぎない。10000以下の素因数を持たない数が見つかると「Xには1万以下の因数がありません。ミラーテストのシークエンスを起動する。飽きたときには、このダイアログでもキャンセルできる。ミラーテストに入るとマシンはちょっと考え込むが、半分以上は「素数でありませんでした。捜索を続けます」とがっかりする報告が出て、予選に戻る。運がよいと「底2の概素数です。底3で確認します」が出る。これが出たらほぼ決まりだ。このデモでは本選の第一次審査は底2、第二次は底3に決めうちしている。このように、予選をやってから有望そうな候補だけをフェルマーテストでじっくり試すのが良い。ジマーマンもPGPでこの二段構えをやっている。フェルマーテストとその強化版(いわゆるミラーテスト)は、ほぼ同じ時間なのでアルゴリズムは長くなるがミラーテストをやるほうが得だ。ミラーにすることで弱擬素数はほとんど弾ける。