isStrongProbablePrime(2)で無罪と出ても、念のためisStrongProbablePrime(3)に控訴する。実際にやれば分かるが、控訴して良かったと思うような悪徳ニセ素数はめったにない。)の両方が入れてあるので、手元でおためしください。デモではPとQと名づける2つの素数を求めて積を作るところまでやる。いちどかけてしまうと、現在の決定性多項式時間アルゴリズムでは、もう二度と分解できないのである。最近のマシンなら1分以内~数分程度のはずだが、確率的なので運もある。表示される時間コストは、ダイアログの時間も含むのでデバッグメッセージを放置しているとその(ユーザの応答待ち)時間も計算時間に含まれる。これは長いアルゴリズムで経過レポートを確実にさせ、途中でアボートもできるようにするためだ。ユーザの応答を待っているアイドル時間をべつにして、正味の計算時間はせいぜい2~3分である。いずれにせよ20桁以上の(たぶん)素数を生成できる。RSA系でいちばん時間を食うのは鍵生成なので、このデモは128ビットや160ビットのRSAをJavaScript上に構成できることを示している。Windows上のJavaScriptホストとしては、MSIEがいちばん速いが、ブラクラを踏まされたと勘違いするのか、うるさい警告が出たりする。4は不安定な点があるが、出力をバッファリングしないでどんどん書き出してくれるのでデバッグには悪くない。MozillaはJavaSciriptの実装が凝っているらしく、かなり時間がかかる。素数でない数が無限に続く区間は無いので、この方法では必ず有限時間で答が出ることは出るが、運が悪いと待たされる。ミラーテストであるから、理論上、底を増やせば必ず正しい判定に達する。本質的にはラスベガスだ。現実の実装では数個の底についてしか計算できない。したがって素数と判定されたものが、じつは間違いで合成数である可能性がわずかにある。現実にはモンテカルロなのだ。失敗といって停止する。半決定可能問題に対するチューリングマシンの動作だ。いっても、まあだいたいは正しいだろうし、だいたいはちゃんと答を出して止まる。やってみれば分かるが、このオーダーのでかい数では、底2で強い概素数になると、まず底3でも概素数と出る。底2で誤審されて底3で逆転有罪になる可能性があるはずなのだが、そういう場面は、めったに見れない。(これは古典的PGPでも同じなのだ。2.6などで鍵を作っているとき、コンソールに*が出るのはフェルマーテストに1回合格のしるしだが、1回合格するとまず4回合格する。いえ20桁オーダーで底が2個だけなので、現実的にわずかながら(カーマイケル数のようなものを掘り当てて)誤審してしまう可能性はある。底を4つに増やせばその確率は非常に小さくなるが、ここではわざと2つにしてある。計算時間を短くするためもあるが、「この素数判定は間違っているかもしれない」ということを味わうことは意義深い。「もしかすると間違っているかもしれない」というリスクを実際に味わってみれば、昨年2002年8月にインドで発見された決定性多項式時間アルゴリズムの重みもよく分かる。鍵生成アルゴリズムが誤作動する可能性を心配するくらいなら、鍵生成中にゴキブリやゴミが筐体に入り込み基盤をショートさせたり、落雷してマシンが壊れる可能性を心配したほうがよっぽど現実的だろう。HDがクラッシュしたり、予期せぬメモリのエラーで間違った答が出る可能性、そもそも鍵を作ってるあいだにユーザが心臓発作でぽっくり逝く確率のほうがよっぽど高い。計算機もまたしかりだ。釈然としないものを残すのは確かだ。ミラーのテストはリーマン予想の拡張版(すごく難しい)を仮定すれば多項式時間なのでたぶん多項式時間だろうが、証明はない。ラビンによる修正版はリーマン予想から独立だが確率的なので絶対に多項式時間で止まるという保証はない。多項式とはいうものの12乗に比例だから現実的には遅すぎる。ソフィージェルマンの予想を仮定すれば6乗に改善されるが、まだ桁が2桁長くなるごとに100倍、4桁で4000倍とかのオーダーだから、あまり速くない。指数的に爆発しないのはすばらしいのだが、すぐに実用になる速さではない。それにひきかえ、ラビン・ミラーの方法だったら、上のデモで20桁から30桁あるいは40桁にしても、そんなに時間は伸びない。数分程度で計算できる。getRandom(20)の20を30や40に書き換えて実験してみてほしい。上のデモはあまり高速化されていない。余りだけ求めればいいときにいつも商も求めていてムダがある。無限精度整数演算のライブラリはそのへんにりっぱなものがあるに決まっている。JavaScriptの上で汚いコードをスクラッチから手作りしなければならないのか、という疑問は当然ありうるだろう。質問に答える必要もないだろう。理屈めいたことを言うなら、.jsファイルでネット上に公開するとはネットがインターフェイスである関数ライブラリを提供することだ。253-1が素数でないことをリアルタイムに示すこともできる。falseこの16桁の数を実際にかたっぱしから割って素数であることを示そうとすると、けっこう面倒だ。そもそもJavaScriptの整数型からはみでてしまう。かけてしまう節操のなさ、日常と数学の境界の破壊には妙味がある。1を17個並べた数が素数かどうか知りたいときに次のように書いてもよい。);</script>128ビットないし160ビットの強さについて初期のPGPには512ビットもあったことを考えると、上記の実装は本物のPGPのレベルにかなり肉薄している。繰り返しになるが、この実装には何ら実用的価値はなく、単におもしろいだけなのだ。人生に明白な意義があるのなら、人生とはひどく退屈なものだったに違いない。nこのページに関するご連絡は、下記メールアドレスへお願いします。メールでのサポートはできませんので、質問がある場合、掲示板をご利用ください。このウェブサイトは、都合により、まもなく終了します。書いてあった情報は、特に断り書きがない限り、自由に使ってください。そのまま転載しても、書き換えたりして再利用してもかまいません。記事の中には情報が古くて現状と合っていないものや、不正確な点を含むものがあるかもしれません。修正が必要と思われる点がありましたら、お気軽にお知らせください。