素数判定機

概要

1000桁以下の自然数の素数の判定を行うツールです。 ※最近は届いたマイナンバーが素数かどうか確認して一喜一憂する遊びに使われているようです。

「決定的素数判定法」は1京未満(16桁以下)の自然数の素数判定ができます (正確には9007199254740991以下の数値の判定になります。 MAX_SAFE_INTEGER(9007199254740991)を超える数値は正確に表せる保証がなく、 9007199254740993以上は最下位ビットが失われ偶数になってしまうためです)

また「確率的素数判定法」として、「フェルマーテスト」は200桁以下の、 「ミラー-ラビンテスト」は1000桁以下の自然数の素数判定ができます。はい、1000桁です。

※類似サービスを提供する他サイトよりも、 (おおむね)より多くの桁をより高速に素数判定ができます。

決定的素数判定法

sample

 

  • 10桁のメルセンヌ素数:2147483647
  • 14桁の大きな素数:92709568269121
  • 16桁の大きな素数:9007199254740997
  • 13桁の合成数:1565912117761 = 1162193×1347377
  • 16桁の合成数:8635844967113809 = 89652331×96325939
※JavaScriptのみで判定しています。入力値のサーバ送信などしていません。

フェルマーテスト

sample

 
a = 2a = 7
a = 3a = 11
a = 5a = 13
フェルマーテスト判定
※フェルマーテストでは「ap−1 ≡ 1 (mod p)」が成り立つとき、「素数かも」と表示。 一つでも「素数ではありません」が表示されたら、素数ではないことが確定。
※サーバに送信しPHPで処理しています。ただし情報の保存等はしていません。

ミラー-ラビンテスト

sample

 

補足

コメント

「決定的素数判定法」は、「1京未満(16桁以下)」を上限としました。 JavaScriptの数値型は内部で倍精度浮動小数点数を使用しており、整数が正確に表せるのは2^53 つまり9,007,199,254,740,992(16桁・約9007兆1993億)までという制約があるので、この機能では一応16桁を上限としました。

9,007,199,254,740,992を超えると偶数になってしまいます。それを確認するサンプルとして、 JavaScriptで正常に表現できる最大の素数「9007199254740881」と JavaScriptで正常に表現できない最小の素数「9007199254740997」をサンプルリストに加えました。

※それ以上の値を計算するためのライブラリもいくつかあるのですが、独自色が強く 信頼性が不明で、またライセンスもよく分からないので、今回は使用を見送りました。

「決定的素数判定法」のアルゴリズムとしては、まず100万以下の素数リストを持ち、 それで割っていき素数リストの最大値を超えたら、2, 3, 5の倍数以外の数で割っていくという、 ハイブリッドの試し割り法です。

当初は処理速度優先で、1000万以下の素数リストを持たせていました。 これだと確かに高速に判定できるのですが、ファイルサイズが5.6MB、 gzip圧縮しても1.6MBと大きめで、初期表示に時間がかかり問題でした。 そのため、処理速度を犠牲にしハイブリッド方式にしました。

処理速度は14桁の素数(92709568269121)で、もともと35msec程度だったのが、 80msec程度と倍以上に遅くなりました。しかし、ファイルサイズが1/10程度になり、 初期表示が比較的スムーズに行えるようになり、さらに対応桁数も2桁増やせたので メリットも大きかったと思っています。

また、JavaScriptで正常に表現できる最大の素数「9007199254740881」の判定も 0.75秒程度(Chrome43, Win7, Core i7)の時間で処理できたので、 最大負荷時の処理性能としても問題ないと判断しました。

「確率的素数判定法」として「フェルマーテスト」と「ミラー-ラビンテスト」を用意しました。 フェルマーテストでは、aを2だけでテストするのではなく、6つの素数を使ってテストをし カーマイケル数を素数と誤判定してしまう様子を確認できるような仕組みにしました。 しかしそのせいで処理速度がかなり遅くなるため、処理上限を200桁としました。

「ミラー-ラビンテスト」は高速に処理できるため上限を1000桁としました。 これにより、RAS暗号で一般的に使用される300~1000桁の値が本当に素数かどうか判定できます。

2種の素数判定はともに、十分なテストを行ったとはいえません。 しかしいくつかの素数で試したことと、その周辺の奇数は素数ではないと判定したこと、 他のサイトと同じ結果を得られたことから、一応問題ないと判断しました。 もし不具合・誤判定があった場合にはその数をぜひ教えていただきたいです。

関連

ちょこっとアンケート&メッセージ

このページに関するちょっとした感想または、要望、バグ・間違いの指摘、 質問・その他お問合せ等は、下記の送信欄からお送りください。 返信をご希望の方は「こちらのページ」からメッセージをお送りください。

「このページはお役に立ちましたか?」のアンケートとメッセージのどちらか一方でかまいません (両方書いていただけるとよりうれしいです)。お気軽にご利用ください (感想・フィードバック・どんな用途で使用したかなどをいただけると作成・運営の励みになります!)


このページはお役に立ちましたか?