素数判定プログラム(2)
巨大素数を検索するJavaScriptプログラム
概要
2005/08/20-2008/12/14
前回素数判定プログラムでは、エラトステネスによってJavaScript上で100万までの素数の一覧を得ることができた。今回では、小さな素数を無数に列挙するのではなく、ある1つの大きな素数を判定してみたい。
今回、開発中の巨大数演算がJavaScript上で巨大な数の巨大累乗の剰余の実装に成功したため、これを用いて巨大素数の判定を行う。またこれによって、JavaScriptの精度(15桁)を超える桁数の素数の判定もできる。
フェルマーテスト
2005/08/20-2008/12/14
今回用いるのは、一般的な素数判定の方法として知られるフェルマーテストだ。これはフェルマーの小定理と呼ばれる次の定理を使う。
フェルマーの小定理
pが素数なら、任意の数nに対してnp-1 ≡ 1 (mod p)が成り立つ
定理についての詳細はフェルマーの小定理 - faireal.net(転載リソース)を参照。ここでは追求しない。
判定したい数をpとして、適当な数nについて上の結果が1なら、その数を素数と判定する。この方法なら、十分大きな領域ではほぼ100%の確率で素数を判別できる。まれに素数でないにも関わらずフェルマーの小定理を満たす擬素数と呼ばれる合成数があるが、巨大自然数ではその確率は無視できる。
フェルマーテストを用いた素数判定プログラム
2005/08/20
このデモは巨大数演算Ver.0.3 alpha9で実装。設定では、一重のフェルマーテストを実行する。前述のように、素数ではないにも関わらずテストをパスする擬素数が存在するため、100%の正確性は保障されない。
桁数が多いと処理に時間がかかるので注意。50桁以下の自然数なら、手元の環境ではそれなりの時間で処理できる。
(2009/06/04)現在はこれより遥かに高速なデモ(HugeInt Ver.0.5-a5)が作られている。擬素数対策もこのページのものよりも強力になっている。
付録:60,80,100桁の検索結果
2005/10/27