巨大数向け素数判定機
フェルマーテスト
※フェルマーテストでは「ap−1 ≡ 1 (mod p)」が成り立つとき、「素数かも」と表示。 一つでも「素数ではありません」が表示されたら、素数ではないことが確定。
ミラー-ラビンテスト
概要
1000桁以下の自然数について素数かどうか判定を行うツールです。
このページでは「確率的素数判定法」として、「フェルマーテスト」と「ミラー-ラビンテスト」で素数判定ができます。
補足
コメント
「確率的素数判定法」として「フェルマーテスト」と「ミラー-ラビンテスト」を用意しました。 フェルマーテストでは複数の数を使ってテストができる仕組みにしました。
最小のカーマイケル数「561」を本ツールでフェルマーテストにかけると、a = 「3, 11, 17」で素数ではないことを確認できます。 「カーマイケル数(Carmichael number)とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数」と定義されています。 この「自身と互いに素である」の部分が重要で、「561」は「3×11×17」の合成数であり、つまり「561」では「3, 11, 17」は定義にあてはまらないわけです。
「フェルマーテスト」はBigInteger.js 、というJavaScriptライブラリを利用させていただきました。 クライアントで計算を行うため、実行するPC・スマホの性能によって、処理速度が大きく変わります。
2019/06に計測したところ1000桁の素数判定で、PC(Core i7-2600)のChromeが1.2秒・Firefoxが73.6秒・Edgeが184秒、 スマホ(SAMURAI MIYABI)のChromeで21.1秒かかりました。 Firefox・Edgeは極端に遅いのでお気をつけください。選択できるならChromeを使用するようにしてください。
「フェルマーテスト」は、「ap−1 mod p」が1であれば素数と判定しますが、 各aに対する計算結果をConsole表示させています。ご興味がある方は「F12」キーで開発者ツールを開き確認してみてください。
「ミラー-ラビンテスト」は、PHPのgmp_prob_primeという関数を使用しています。手軽に利用でき、比較的高速に処理できるため採用しました。
サンプルにある「RSA-129」は1977年、RSA暗号の発明者の一人であるロナルド・リベスト博士が発表した懸賞問題です。 当時、解読には2万年は必要だろうと予測されていましたが、掲載から17年後の1994年に 多重多項式ふるい法という方法 によって、合成数であると解読されました。
関連・参考リンク
ちょこっとアンケート＆メッセージ
このページに関するちょっとした感想または、要望、バグ・間違いの指摘などは、下記の送信欄からお送りください。 質問・その他お問合せなど、返信をご希望の方は「こちらのページ」からメッセージをお送りください。
「このページはお役に立ちましたか？」のアンケートと自由メッセージのどちらか一方でかまいません (両方だとよりうれしいです)。お気軽にご利用ください (感想・どんな用途で使用したかなどをいただけると作成・運営の励みになります！)。
このページはお役に立ちましたか？
画像のひらがな一文字を入力してください。拗音・促音・濁点・半濁点はありません。
※サンプルの追加・ツール改善の参考に利用させていただきます。