(2003-05-24)JavaScript上で、1分程度で20~40桁の素数を見つける確率的アルゴリズムを実装し、計算の複雑性理論についていくつかの実感をつかむ。先に進む前に、関連する話題として、ミラー(Miller)の素数判定法と強擬素数(きょうぎそすう)に触れておく。フェルマーテストは実用上それなりに有効だ。素数でない数(合成数)のほとんどはフェルマーテストでふるい落とされる。素数でないにもかかわらずフェルマーテストに合格する「擬素数」がわずかながら存在する。「ニセ素数」に対する耐性がかなり向上する。n-1を2で割って......ミラーテストの原理は単純だ。