巨大数向け素数判定機

ミラー-ラビンテスト

sample

 

概要

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

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

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

補足

コメント

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

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

サンプルにある「RSA-129」は1977年、RSA暗号の発明者の一人であるロナルド・リベスト博士が発表した懸賞問題です。 当時、解読には2万年は必要だろうと予測されていましたが、掲載から17年後の1994年に 多重多項式ふるい法という方法 によって解読されました。

関連・参考リンク

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

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

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


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