前 7 - 02 p ｜ 
もくじ i ｜ 次 7 - 04 n 
「RSA暗号と
巨大な整数が素数か素数でないかを知るのに、 フェルマーテストは実用上それなりに有効だ。 素数でない数（合成数）のほとんどはフェルマーテストでふるい落とされる。 しかし素数でないにもかかわらずフェルマーテストに合格する「擬素数」がわずかながら存在する。
ミラーテストはフェルマーテストの改良版のようなもので、 フェルマーテストより多少計算量は増えるかわりに、 「ニセ素数」に対する耐性がかなり向上する。
ミラーテストの原理は単純だ。
たとえば、n = 12377 を例に考えてみる。
この数は素数だ。
ミラーテストでは検査したい数 n より1小さい数 n-1 に注目する。
いま考えている例では、n-1 = 12376。
これを2で割れるだけ割る。
12376 ÷ 2 = 6188
6188 ÷ 2 = 3094
3094 ÷ 2 = 1547
ここで商が奇数になって、もうこれ以上2では割れない。要するに、
12377 = 23×1547
この計算で出てきた４つの数――
1547, 3094, 6188, 12376
のうち、初めの数は n-1 を2で割れるだけ割って残った奇数、
最後の数は n-1 そのもので、となりあう項は次々と2倍、2倍の関係になってる。
これらをある自然数 b 例えば2の肩に乗せてみると――
21547, 23094, 26188, 212376
――この最後の数 212376 は n が素数のときの n-1 乗なので、
フェルマーの定理から ≡1 (mod n) だ。
212376 ≡ 1 (mod 12377)
さて、いま考えている数列、
21547, 23094, 26188, 212376
は、指数（肩の数）が2倍2倍に増えていく列なので、全体としては前の数の2乗が次の数になっている。例えば
(21547)2 = 21547×2 = 23094
これを mod 12377 で考えると、最後の項 212376 は ≡1 なのだから、 そのひとつ前の項は二乗して ≡1 になるような数でなければならない。 つまりひとつ前の数も ≡1 であるか、または ≡ -1 つまり ≡12376 (mod 12377) ではないかと思いつく。 もしひとつ前の数が ≡1 であるとしたら、同じ理屈から、そのさらにひとつ前は ≡±1 ではないか？ この推測は、ある意味で正しく、ある意味で正しくない。 詳しく考える前にとりあえず実際の数値例で調べてみよう。
<script type="text/javascript"> _debug( Bigint.powmod( 2, 1547, 12377 ) ); _debug( Bigint.powmod( 2, 1547*2, 12377 ) ); _debug( Bigint.powmod( 2, 1547*4, 12377 ) ); _debug( Bigint.powmod( 2, 1547*8, 12377 ) ); </script>
結果 Debug: 12376. Debug: 1. Debug: 1. Debug: 1.
次々に前の数の二乗になってゆく列
21547, 23094, 26188, 212376
は、mod 12377 においては、
-1, 1, 1, 1
と合同であることが分かった。最初の-1を二乗すると1、あとは何度二乗しても1の二乗は1、という関係になっている。底を3にして、
31547, 33094, 36188, 312376
で同じ実験をしてみる。
<script type="text/javascript"> _debug( Bigint.powmod( 3, 1547, 12377 ) ); _debug( Bigint.powmod( 3, 1547*2, 12377 ) ); _debug( Bigint.powmod( 3, 1547*4, 12377 ) ); _debug( Bigint.powmod( 3, 1547*8, 12377 ) ); </script>
結果 Debug: 11703. Debug: 8704. Debug: 12376. Debug: 1.
今度は3項めで 12376≡-1 が現れた。そのひとつ前は「2乗すると≡12376 になる数」だが、さしあたって、この数には興味ない。
この例では、1547×8乗 つまり 12376乗、言い換えれば n-1 乗して初めて≡1になる。
いずれにしても n が素数なら初めて≡1になる場所の一個前の項は、≡-1 だ。
ただし最初の項からすでにいきなり ≡1 になっている場合は「一個手前」がそもそも存在しないので、例外。
まとめると、n が素数である限りにおいて、
上の形の数列を mod n で考えると、
1, 1, 1, ... , 1
のようにぜんぶ ≡1 か、あるいは、
... , -1, 1, 1, ... , 1
のように、どこか途中（最初でもいい）で ≡ -1 が現れて、そこ以降はぜんぶ ≡1 になるか、のいずれかだ。
以下でこのことをきちんと証明しよう。
何をきちんとしたいかというと、いま、「ある数 x を平方したら≡1になるとき、x ≡±1 であろう」と考えているのだが、
このことは本当は一般には正しくない。例えば、3の2乗は9だから、mod 8 で考えると、
32 ≡ 1 (mod 8)
であって、±1以外の数（ここでは3）を二乗したら≡1ということが実際ありうる。
このように、剰余類の上での算術では、
通常の数体（例えば有理数）の上での算術ではあり得ないような「変なこと」（1でも-1でもないくせに、二乗すると1になる）が起きて話がややこしくなるようだが、
ミラーテストはむしろこのことを逆用する。簡単にいうと、n が素数なら「変なこと」は起こらず、二乗して1になるものは±1なのだが、
n が素数でない場合には上に見たように一般にこのことは成り立たず「変なこと」が起きてくるので、
「変なこと」が起きていたら n は素数であり得ない、と判定できる。
抽象的にいうと、n が素数の場合の剰余類 Zn はいろいろな意味で n が合成数の場合とは異なる特別な構造を持っている。
かたい話はともかく、2以上の自然数 b を二乗して ≡1 (mod n) になるということは、
b2 を n で割ると1余る
ということだから、1引いたら余りが出ないできっかり割り切れる:
b2-1 は n で割り切れる
ということだ。ここで a2-b2 = (a+b)(a-b) という公式を使うと、
b2-1 = (b+1)(b-1)
となるが、左辺は n で割り切れるので、もし n が素数ならば左辺を素因数分解したら必ず n という因数が出る。
また b は自然数なので、 右辺にある (b+1) と (b-1) はどちらも自然数であり、この積を素因数分解したらもちろん左辺と同じ結果になるのだから、
(b+1) か (b-1) かのどっちかかから素因数 n が出ることになる。
ということは、b+1 か b-1 の一方は n の倍数で、言い換えれば
b+1 ≡ 0 または b-1 ≡ 0 (mod n)
b ≡ -1 または b ≡ 1 (mod n)
まとめると、n が素数なら、mod n で「二乗して≡1」になる数は≡±1だ。
ここで n が素数ならという仮定が効いていることに注意してほしい。
n が素数でない場合、例えば n=6 のとき、
b2-1 = (b+1)(b-1)
が6で割り切れるからといって、(b+1) または (b-1) のどちらかは6の倍数だとは言い切れない。
b+1、b-1のどちらも6の倍数でないにもかかわらず、例えばb+1が2の倍数でb-1が3の倍数だと(b+1)(b-1)は6の倍数になれる。
6という因数を2と3に分解して格納できるのだ。
しかし例えば n=7（素数）のときは、7はこれ以上分解できないので、
b+1、 b-1 のどちらか一方が必ず7という素因数を持たざるを得ない。
そんなわけで法が素数であるかどうかで違う代数構造になる。
「n が素数のときミラーの数列には（初項が1でない限り） -1 が現れる」ということを証明しよう。まず問題をきちんと言い表しておく。
3以上のある奇数 n が与えられたとして、その数から1を引いた偶数 n-1 を2で割れるだけ割って次の形に書く:
n-1 = 2ks （s は奇数）
このとき、次の数列を mod n で考えると、
もし n が素数なら、全部の項が≡1 であるか、さもなければ、最後の項より前のどれかの項が≡-1 でそれ以降の項は全部 ≡1 になる。
2s, 22s, 222s, 223s, ... , 22k-1s, 22ks
指数部分にまた指数があってちょっと見づらいが、要は2の肩に
20s, 21s, 22s, ..., 2k-1s, 2ks
が乗っている。
n が素数ならフェルマーの定理によって
22ks = 2n-1 ≡ 1 (mod n)
であることは分かっているから、最後の項は ≡1 になる。
最後の項はそのひとつ手前の項の二乗であるが、
すでに見たように法 n が素数のとき二乗した結果が≡1になるのは、もとの数が≡1または≡-1のときに限られる。
したがって最後の項よりひとつ手前の項は≡1または≡-1である。
もし≡-1なら証明は完了する。さもなければその項は≡1であり、そのまた前の項（もしあれば）の二乗であるから、
同じ議論によってそのまた前の項は≡1または-1である。
このようにしてどこかで≡-1になれば証明は完了する。
さもなければ、そのまた前そのまた前と進んでついにいちばん最初の項までぜんぶ≡1ということになる。
以上がまさに示したいことであった。
上の例では具体的に分かりやすく底 b を2に固定したが、 底は2以上で n と互いに素なら何でも良い。 実際、上の証明では b=2 という事実は使っていない。 例えば n が 3 でも 5 でも割り切れないことを確認したら、 3 や 5 を底にして良い。素数性判定をしたいのだから、n が 3 や 5 のような小さい素数で割り切れるなら、 そもそもテストの意味がない。 mod n で考えるので、b < n と仮定しても一般性は失われないが、 実際問題 n は大きな（例えば100桁の）整数なので、大きい底は計算量的にも現実的でもない。
ある（大きな）奇数 n が与えられたときに上のような数列を作るとする。 で、最初の項が≡1になったら、以下計算するまでもなくぜんぶの項が≡1になるのでその数は合格。 また最初の項か途中の項で≡-1が出たら、それも合格で、そこで計算をやめていい。 他方、最後の項のひとつ手前まできても≡-1が一度も現れない場合、その時点でミラーテスト失格となる。
フェルマーテストでふるい落とされるような合成数は、 絶対にミラーテストに合格できない。 実際、ミラー数列のどこかに1が現れることはミラーテスト合格の必要条件であり、 しかもそれだけではまだ充分でない。 フェルマーテストで落ちる数に対してはミラー数列のどこにも1が現れないのだから、必要最低基準さえ満たさず、お話にならない。 もしミラー数列のどこかに1が現れるとすると数列のその項以降は1になって第k項（最後の項）が1になるが （法nが素数でなくても≡1の数を二乗すれば≡1なので）、 これはフェルマーテストに合格できることを意味している。 したがってフェルマーテストに合格できない数はミラー数列に1が現れず、当然にミラーテストにも合格できない。
次に素数でないくせにフェルマーテストを合格してしまう数、いわゆる擬素数も、 ミラーテストにかけるとほとんどふるい落とされる。 ミラーテストは本質的に「素数 n に対する剰余類が持ち得ない性質」――±1でない類の平方が1になるという性質――を検出しようとする。 ミラーテストに合格するためには、ミラー数列のどこかに1が現れなければならないが、 最初に1が現れる項のひとつ前の項は≡-1であることを要求される。 ±1でないものを二乗して≡1になる、などというのは素数を法とする秩序正しい世界では起こり得ないからである。 ただし、初項からすでに1の場合、この性質についての検証を行うことができない。 また、法 n が素数でないにもかかわらずミラー数列で初めて1が現れる場所のひとつ手前がたまたま≡-1ということが考えられる。 というのも、法 n が素数でなくても、-1 と合同な数の二乗が 1 と合同になるのは確かだからだ。 ±1以外の数の二乗が≡1になれば法が素数でないと断定できるが、 逆に「法が素数でないならつねに二乗すると1になる±1以外の類が存在する」とは断定できないし、 そもそもミラー数列のような（ある剰余類における）ほんの少しの計算例だけでその剰余類の代数構造（「非自明な1の平方根」を持つかどうか） を確定できるわけではない。
そうは言っても、素数でないくせにミラーテストをあざむくのは相当に難しい。 単にフェルマーの小定理の逆を満たすだけでなく、 「Znに非自明な1の平方根がある」というしっぽを出さないようにしなければならないからだ。 理論上、いろいろな底に対してミラーテストを実行すると、 ニセ素数は必ずどこかで、テストに失敗するか、 またはフェルマーテストをあざむく擬素数であっても「非自明な1の平方根の存在」をさらけだし、化けの皮がはがれる。 これに対して、フェルマーテストの場合、底をいろいろ変えても素数のふりをし通せるような「とんでもないニセ素数」が存在するのである。 ただし、純粋数学を離れてRSA暗号への現実的応用を考えると、 n は100桁のような巨大な整数であるから、すべての可能な底に対して検査を行うどころか、 その一億分の一の検査すら非現実である。 また、ミラーテストまでしなくても、フェルマーテストでも、充分に実用的ではある。 フェルマーテストをあざむくような擬素数そのものがかなりまれだからだ。
ミラーのテストに合格する数は、強力な素数候補と呼ばれる。
強力な素数候補と認定される数のほとんどすべては実際に素数である。
実際には素数でないのに強力な素数候補にノミネートされてしまうようなずうずうしい数を
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911
このうち強擬素数は 2047, 3277, 4033, 4681, 8321 の5個である。
1387 = 19×73 は素数ではないがフェルマーテストによって素数候補となる擬素数である。 しかしミラーテストは通過できない。
<script type="text/javascript"> // 1387-1 = 1386 = 2×693 _debug( Bigint.powmod( 2, 693, 1387 ) ); _debug( Bigint.powmod( 2, 693*2, 1387 ) ); </script>
結果 Debug: 512. Debug: 1.
2行めは Bigint.powmod( 2, 1387-1, 1387 ) に相当し、フェルマーテストにあたる。
確かに剰余1を返し、素数候補だ。
しかし、その「平方根」が±1 でなく 512 という「変な」値になっているのでミラーテストで、はねられてしまう。
512×512 = 262144 ≡ 1 (mod 1387)
次に強擬素数 4033 = 37×109 に対するミラーテストを試してみよう。
4033-1 = 4032 = 64×63 だ。
<script type="text/javascript"> _debug( Bigint.powmod( 2, 63, 4033 ) ); _debug( Bigint.powmod( 2, 63*2, 4033 ) ); _debug( Bigint.powmod( 2, 63*4, 4033 ) ); _debug( Bigint.powmod( 2, 63*8, 4033 ) ); _debug( Bigint.powmod( 2, 63*16, 4033 ) ); _debug( Bigint.powmod( 2, 63*32, 4033 ) ); _debug( Bigint.powmod( 2, 63*64, 4033 ) ); </script>
結果 Debug: 3521. Debug: 4032. Debug: 1. Debug: 1. Debug: 1. Debug: 1. Debug: 1.
第2項で 4032≡-1 になり、-1の平方として第3項以降で「もっともらしく」≡1 になっている。 まったく素数にしか見えない。 腹が立つので底を3に変えて化けの皮をはがしてやろう。
<script type="text/javascript"> _debug( Bigint.powmod( 3, 63, 4033 ) ); _debug( Bigint.powmod( 3, 63*2, 4033 ) ); _debug( Bigint.powmod( 3, 63*4, 4033 ) ); _debug( Bigint.powmod( 3, 63*8, 4033 ) ); _debug( Bigint.powmod( 3, 63*16, 4033 ) ); _debug( Bigint.powmod( 3, 63*32, 4033 ) ); _debug( Bigint.powmod( 3, 63*64, 4033 ) ); </script>
結果 Debug: 3551. Debug: 2443. Debug: 3442. Debug: 2443. Debug: 3442. Debug: 2443. Debug: 3442.
底を3に変えるとフェルマーの（弱い）擬素数にすらならないことが分かる（最後の項まで来ても≡1にならない）。 複数の底に対して擬素数でありつづけることは非常に難しいのだ。 なお、この記事では分かりやすくベタでリストを書いたが、実際には大きな指数計算を何度もする必要ない。 「前の項の二乗」の剰余は、「前の項の剰余の二乗」の剰余に等しいので、次のように計算量を大幅に節約できる。
<script type="text/javascript"> var a0 = Bigint.powmod( 3, 63, 4033 ); var a1 = Bigint.powmod( a0, 2, 4033 ); var a2 = Bigint.powmod( a1, 2, 4033 ); var a3 = Bigint.powmod( a2, 2, 4033 ); var a4 = Bigint.powmod( a3, 2, 4033 ); var a5 = Bigint.powmod( a4, 2, 4033 ); </script>
実装上、最初の項で1になれば、その段階で合格となり、以下続けても結論は変わらないので、ただちに中止して良い。 そうでない場合、-1が出ればその段階で合格となり、以下続けても結論は変わらないので、そこで中止して良い。 最後の項のひとつ手前まで来ても-1にならないなら、その段階で不合格である。 最後の項のひとつ手前が ≡±1 でなくても最後の項が≡1になることはありうるが（フェルマーの擬素数の場合）、 この場合は絶対に本物の素数でないので どっちにしても最後の項は実際に計算する必要ない。 理論上、途中で1が出てその前の項が≡±1でなかったなら、本物の素数でないと判断できるので、そこで中止できる。 途中で1が出たらそのあとは1の二乗（つまり1）の剰余（つまり1）を求めるだけなので、 実装上、1が出た瞬間にやめても計算量を極端に減らせるわけではない。
異なる底に対してミラーのテストを反復することを、一般にラビン・ミラー（Rabin-Miller）のテストという。
ラビンによれば、ある底に対してミラーのテストが誤判定（素数でないものを合格させてしまうこと）をする確率は最大でも 1/4 であるという。
したがって、理論的には、ラビン・ミラーテストにより「素数性品質」を定量的に管理できる。
例えば、5つの異なる底に対して有効なミラーのテストをパスした数が「不良品」（実は素数でなかった）という確率は最悪でも
(1/4)5 ≒ 0.00098
となる。理論上、フェルマーテストの場合、すべての有効な底に対してどれでやっても擬素数になる可能性が極めてわずかながらある。
ミラーテストを使った巨大な整数の素数性判定では、底の数を増やせば失敗確率を望むだけ小さくできる。
2003年に書かれた記事です。 128ビットのRSAを JavaScript 上で構築する道筋を示しています。 2004年には、ずっと強い1024ビットのRSAを、もっと効率的に実装できるようになりました。 したがって、「JavaScript: 触って分かる公開鍵暗号RSA」（2004年2月）を先に読まれたほうが、 分かりやすいかもしれません。この古い記事も、参考として残しておきます。
JavaScript上で、1分程度で20～40桁の素数を見つける確率的アルゴリズムを実装し、計算の複雑性理論についていくつかの実感をつかむ。 少なくとも128～160ビットの鍵を生成できる。
2000年ごろのふつうのPC（Pentium Ⅲ 850 MHz）では、エラトステネスのふるいを使ったがむしゃらなアルゴリズムで、10進16桁の素数を2～3分で発見し、 100ビットのRSA暗号をJavaScript上に構成できた。 64ビットについてはJavaScriptだけで完全なアプリケーション・インターフェイスを構築することさえできた。 エラトステネスのふるい自体は疑問の余地のない確定的なアルゴリズムではあるが、JavaScript自身の組み込み関数ではおよそ53ビット超の整数は扱えないので、 足し算、掛け算といったところから自前で準備しなければならない。 また、ふるいの方法の計算時間は、桁数についての多項式では済まず、指数時間だ。 桁数が2桁長くなるごとに計算時間が10倍、4桁長くなると100倍、6桁長くなると1000倍、 8桁長くなると1万倍……という途方もない勢いなので、100ビットがぎりぎりという状況では、104ビットや108ビットというわずかな前進も、もはや困難である。 （ぎりぎり待てる限度の100倍や1万倍の時間は待てない。） どうしてそうなるかと言えば、桁数が2桁伸びるごとにふるいでは割り算の数が明らかに約10倍になるからだ。
したがって、2003年現在、先に進むには通常、確率的アルゴリズムを使う。
現実によく使われるのはフェルマーテストまたはその強化版だ。
フェルマーテストと
bN-1≡1 (mod N)
を満たすかどうか確かめれば良い。これを満たさないなら絶対に素数でないので、実際に因数を知ることなく、合成数であると断定できる。
われわれの道具箱には、でかい数A, B, Cについて「AをB乗してCで割った余りを求める」
Bigint.powmod()
がすでに入っているので、速度はイマイチだが、上記のことはほんの数行の手間だ。
Bigint.prototype.isProbablePrime = function( oBase ) {
var oResult = Bigint.powmod( oBase , this.minus( 1 ), this );
return ( oResult.isEqualTo(1) ) ;
}
これがfalseを返すものは確実に合成数であるから捨てる。 trueが返った場合は「たぶん」素数だ。
このデモをいじくることで、計算の複雑さの理論（複雑性理論）、とくに確率的チューリングマシンのふるまいや、ラスベガス、モンテカルロの意味について、 教科書を読んでも得られないようななまなましい実感が体得できるだろう。 なお、JavaScriptの実演なので、もちろんJavaScriptが有効なブラウンジング環境が必要。CPUに負荷がかかるので注意。
まずページを開くと「素数を探します。数分かかる可能性があります。」というダイアログが出る。
これは間違えて起動してしまったときにキャンセルするためのもので、たいした意味はない。
ここで「第一の素数を探しています...」と表示されて確率的な探索が始まる。
このデモでは20桁の乱数を発生させて、ミラーとラビンによる反復的・強化版フェルマーテストを行う。
しかしその前段階として、エラトステネスのふるいを軽くかけて、10000以下の素数で割れるものは飛ばす。
[63908 83314 43524 40433] Skipped (7)...[63908 83314 43524 40439] Skipped (13)...
のようなデバッグメッセージが出るのは、［］内の20桁の数が()の小さい素数で割れてしまって予選落ちしたことを意味する。
なお2で割れるもの（偶数）は最初から無視され、3や5で割れるものは予選の予選で落とされるので、デバッグメッセージに乗るのは最低でも7の倍数以上になっているが、
この点には深い意味はない。これでわずかに割り算を節約できるかもしれないが、
意図としては単にデバッグメッセージがごちゃごちゃしすぎないように、そうしているにすぎない。
10000以下の素因数を持たない数が見つかると「Xには1万以下の因数がありません。素数かも知れないので調べてみます」と期待させるダイアログを出して、 ミラーテストのシークエンスを起動する。飽きたときには、このダイアログでもキャンセルできる。 ミラーテストに入るとマシンはちょっと考え込むが、半分以上は「素数でありませんでした。捜索を続けます」とがっかりする報告が出て、予選に戻る。 運がよいと「底2の概素数です。さらに底3で確認します」が出る。これが出たらほぼ決まりだ。 このデモでは本選の第一次審査は底2、第二次は底3に決めうちしている。
フェルマーテストは遅いから、
このように、予選をやってから有望そうな候補だけをフェルマーテストでじっくり試すのが良い。
ジマーマンもPGPでこの二段構えをやっている。
フェルマーテストとその強化版（いわゆるミラーテスト）は、ほぼ同じ時間なのでアルゴリズムは長くなるがミラーテストをやるほうが得だ。
ミラーにすることで弱擬素数はほとんど弾ける。
そして複数回やる。これは擬素数対策。さすがに1回だけだと「たまたま擬素数だった」ときホントは有罪の犯人がRSAシステムに入り込んでしまうので、
isStrongProbablePrime(2)で無罪と出ても、念のためisStrongProbablePrime(3)に控訴する。実際にやれば分かるが、控訴して良かったと思うような悪徳ニセ素数はめったにない。そのライブラリには、
isProbablePrime( base )
isStrongProbablePrime( base )
の両方が入れてあるので、手元でおためしください。
デモではPとQと名づける2つの素数を求めて積を作るところまでやる。 この積まではどうやら多項式時間でできるのだが、 いちどかけてしまうと、現在の決定性多項式時間アルゴリズムでは、もう二度と分解できないのである。 RSAの本質はこの一言に尽きる。
計算時間は最近のマシンなら1分以内～数分程度のはずだが、確率的なので運もある。 表示される時間コストは、ダイアログの時間も含むのでデバッグメッセージを放置しているとその（ユーザの応答待ち）時間も計算時間に含まれる。 これは長いアルゴリズムで経過レポートを確実にさせ、途中でアボートもできるようにするためだ。 ユーザの応答を待っているアイドル時間をべつにして、正味の計算時間はせいぜい2～3分である。
いずれにせよ20桁以上の（たぶん）素数を生成できる。 RSA系でいちばん時間を食うのは鍵生成なので、このデモは128ビットや160ビットのRSAをJavaScript上に構成できることを示している。 Windows上のJavaScriptホストとしては、MSIEがいちばん速いが、ブラクラを踏まされたと勘違いするのか、うるさい警告が出たりする。 Netscape 4は不安定な点があるが、出力をバッファリングしないでどんどん書き出してくれるのでデバッグには悪くない。 MozillaはJavaSciriptの実装が凝っているらしく、かなり時間がかかる。
素数でない数が無限に続く区間は無いので、この方法では必ず有限時間で答が出ることは出るが、運が悪いと待たされる。 ミラーテストであるから、理論上、底を増やせば必ず正しい判定に達する。 本質的にはラスベガスだ。しかしそれは理論であって、 現実の実装では数個の底についてしか計算できない。
したがって素数と判定されたものが、じつは間違いで合成数である可能性がわずかにある。 現実にはモンテカルロなのだ。そして、ある種の怠けから、最初の乱数から1000を足した区間にまで素数がないと、 失敗といって停止する。半決定可能問題に対するチューリングマシンの動作だ。 といっても、まあだいたいは正しいだろうし、だいたいはちゃんと答を出して止まる。 やってみれば分かるが、このオーダーのでかい数では、底2で強い概素数になると、まず底3でも概素数と出る。底2で誤審されて底3で逆転有罪になる可能性があるはずなのだが、そういう場面は、めったに見れない。（これは古典的PGPでも同じなのだ。PGP 2.6などで鍵を作っているとき、コンソールに*が出るのはフェルマーテストに1回合格のしるしだが、1回合格するとまず4回合格する。） とはいえ20桁オーダーで底が2個だけなので、現実的にわずかながら（カーマイケル数のようなものを掘り当てて）誤審してしまう可能性はある。 底を4つに増やせばその確率は非常に小さくなるが、ここではわざと2つにしてある。 計算時間を短くするためもあるが、「この素数判定は間違っているかもしれない」ということを味わうことは意義深い。 「もしかすると間違っているかもしれない」というリスクを実際に味わってみれば、昨年2002年8月にインドで発見された決定性多項式時間アルゴリズムの重みもよく分かる。
（このデモでなく）実際のRSAが間違っている（鍵が保証書に書いてある能書きに比べて壊れやすい可能性がある）ということは、
ないと言って良い。
鍵生成アルゴリズムが誤作動する可能性を心配するくらいなら、鍵生成中にゴキブリやゴミが筐体に入り込み基盤をショートさせたり、落雷してマシンが壊れる可能性を心配したほうがよっぽど現実的だろう。きちんと計画された確率的素数判定が誤審をする可能性を疑うより、鍵の生成中に例外が発生してブルースクリーンが出たり、
HDがクラッシュしたり、予期せぬメモリのエラーで間違った答が出る可能性、そもそも鍵を作ってるあいだにユーザが心臓発作でぽっくり逝く確率のほうがよっぽど高い。巨視的世界のできごとは常にあやふやであり、
計算機もまたしかりだ。そうは言うものの、確率的に間違う可能性があるアルゴリズムが理論的、心理的、思弁的に釈然としないものを残すのは確かだ。
ミラーのテストはリーマン予想の拡張版（すごく難しい）を仮定すれば多項式時間なのでたぶん多項式時間だろうが、証明はない。
ラビンによる修正版はリーマン予想から独立だが確率的なので絶対に多項式時間で止まるという保証はない。
アグラワル・カヤル・サクセナはリーマン予想から独立かつ非確率的な、多項式時間そのものだが、
多項式とはいうものの12乗に比例だから現実的には遅すぎる。ソフィージェルマンの予想を仮定すれば6乗に改善されるが、まだ桁が2桁長くなるごとに100倍、4桁で4000倍とかのオーダーだから、あまり速くない。指数的に爆発しないのはすばらしいのだが、すぐに実用になる速さではない。
それにひきかえ、ラビン・ミラーの方法だったら、上のデモで20桁から30桁あるいは40桁にしても、そんなに時間は伸びない。数分程度で計算できる。
getRandom(20)の20を30や40に書き換えて実験してみてほしい。
上のデモはあまり高速化されていない。特に余りを求める関数が手抜きで「商と余りを求める関数」の商を捨てて余りだけ使っているので、 余りだけ求めればいいときにいつも商も求めていてムダがある。
こういうことはCやC++でやれば速いし、Perlであれ何であれ、 無限精度整数演算のライブラリはそのへんにりっぱなものがあるに決まっている。 なぜJavaScriptの上で汚いコードをスクラッチから手作りしなければならないのか、という疑問は当然ありうるだろう。 しかし、そのようなばかげた疑問を持つ「賢明」な読者はそもそもこの記事をここまで読むわけがないから、 質問に答える必要もないだろう。
理屈めいたことを言うなら、.jsファイルでネット上に公開するとはネットがインターフェイスである関数ライブラリを提供することだ。 例えば、ウェブで日記をつけている人が、HTML上にじかに次のように書いて、 253-1が素数でないことをリアルタイムに示すこともできる。
<script type="text/javascript">
A = ( Bigint.pow( 2 , 53 ) ).minus(1);
_Debug( "2の53乗ひく1" , A );
_Debug( "3を底としてたぶん素数？", A.isProbablePrime(3) );
</script>
出力例
2の53乗ひく1 : 9 00719 92547 40991 3を底としてたぶん素数？ : false
この16桁の数を実際にかたっぱしから割って素数であることを示そうとすると、けっこう面倒だ。
そもそもJavaScriptの整数型からはみでてしまう。Cのプログラムや、数学ソフトを使ってあれこれすることの意義は否定できないが、
それでもHTMLページのなかに直接 .isProbablePrime(3) とかけてしまう節操のなさ、日常と数学の境界の破壊には妙味がある。
例えば、1を17個並べた数が素数かどうか知りたいときに次のように書いてもよい。
<script type="text/javascript">
myNumber = Bigint.Number( "11 11111 11111 111111" );
_Debug( myNumber.isProbablePrime() ? "たぶんね" : "ちがうよ" );
</script>
初期のPGPには512ビットもあったことを考えると、上記の実装は本物のPGPのレベルにかなり肉薄している。 しかし、繰り返しになるが、この実装には何ら実用的価値はなく、単におもしろいだけなのだ。 もし人生に明白な意義があるのなら、人生とはひどく退屈なものだったに違いない。どれいのように。
