巨大素数を検索する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)が作られている。擬素数対策もこのページのものよりも強力になっている。
2005/10/27
このプログラムは任意の桁数の素数を検索する。RSAの下準備に近い。Mozillaでは水色のボックスに、IEではステータスバーに処理内容が表示される。発見された素数はPrimeに出力され、処理の詳細はテキストエリアに出力される。
このデモは巨大数演算Ver.0.3 alpha9で実装した。
デモの具体的な処理内容を解説する。まず1万までの素数表を用いてランダムに選ばれた候補数を割れるかテストし、1万まで割っても割り切れなかったら本命のフェルマーテストで判定する。フェルマーテストは計算量が非常に多いので、エラトステネスである程度ふるい落としてから行う。
これをパスした数が素数として出力される。なお15桁以内の場合最初のエラトステネスはJavaScriptの組み込み関数で行うが、16桁を越えると全計算を巨大数演算を用いて処理するので若干速度が落ちる。
現在はこのデモより遥かに高速なデモ(HugeInt Ver.0.4)が作られている。(2005/12/17)
2005/10/27