巨大数向け素数判定機

フェルマーテスト

sample

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

ミラー-ラビンテスト

sample

 

概要

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

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

補足

コメント

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

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

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

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

関連

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

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

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


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