巨大数向け素数判定機

ミラー-ラビンテスト

sample

 

概要

1000桁以下の自然数について素数かどうか判定を行うツールです。

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

※フェルマーテストは現在調整中です(2018/08現在)

補足

コメント

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

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

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

当初は「決定的素数判定法」「フェルマーテスト」「ミラー-ラビンテスト」の3機能を 1つのページにまとめていたのですが、内容が多いので、 「素数判定機 (決定的素数判定法)」と 「巨大数向け素数判定機 (フェルマーテスト・ミラー-ラビンテスト)」で別のページに分離しました。

関連・参考リンク

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

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

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


このページはお役に立ちましたか? ※サンプルの追加・ツール改善の参考に利用させていただきます。 チェックを入れなければ値の送信はせず、メッセージのみの送信となります。