ミラーテストと強擬素数(きょうぎそすう) (2003-01-29) 128ビットRSAの鍵生成のデモ: JavaScript (2003-05-24) JavaScript上で、1分程度で20~40桁の素数を見つける確率的アルゴリズムを実装し、計算の複雑性理論についていくつかの実感をつかむ。 「RSA暗号と擬素数(ぎそすう) - JavaScript」では、 巨大な整数が素数であるかどうか調べる「確率的」検査法、フェルマーテストを強引に JavaScript 上にもちこんだ。 先に進む前に、関連する話題として、ミラー(Miller)の素数判定法と強擬素数(きょうぎそすう)に触れておく。 ミラーのテスト 巨大な整数が素数か素数でないかを知るのに、 フェルマーテストは実用上それなりに有効だ。 素数でない数(合成数)のほとんどはフェルマーテストでふるい落とされる。 しかし素数でないにもかかわらず