ForHosting KIT · 数学

決定的 Miller–Rabin 判定

97は素数です。2、3、5、7、11、13、23の7つの固定基底をすべて通過し、これらは9007199254740991までのすべての整数を確実に判定できると証明されています。合成数なら、それを見抜いた最初の基底も表示します。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
N
97
結果
境界
9,007,199,254,740,991
証人の数
7

決定的 Miller–Rabin 判定は、公開された保証上限未満のすべての整数を決着させることが知られている短い固定の基底リストに対して、強いおそらく素数の証人検査を実行し、整数 n が素数かどうかを決めます。乱数の証人を引き誤差だけを見積もる確率的 Miller–Rabin とは異なり、本機能は常に同じ基底を使い、同じ n には常に同じ判定を返し、それらの基底が十分と証明されなくなる上限を超える入力は拒否します。少なくとも 2、多くとも上限までの整数を 1 つ送ると、素数フラグ、証人リスト、上限そのもの、そして合成数の場合にはそれを示した最初の証人が返ります。

固定基底の強いおそらく素数検査の仕組み

Miller–Rabin は奇数の候補 n を、d が奇数である n マイナス 1 イコール d かける 2 の s 乗として書き換え、各証人 a について a の d 乗を n で割った余りを計算します。その冪が 1 または n マイナス 1 なら証人は合格です。

そうでなければアルゴリズムは値を最大 s マイナス 1 回まで二乗し、途中の二乗が n マイナス 1 と等しいときだけ証人を受け入れます。それ以外の経路はその基底について n が合成数であることを証明します。すべての証人に合格する数は、それらの基底に対する強いおそらく素数と呼ばれます。

注意深く選ばれた固定集合では、既知のしきい値未満に集合内のすべての基底を欺く合成数は存在しないという数論の結果があり、したがっておそらく素数という結果は上限内では真の素数判定になります。本機能は 2、3、5、7、11、13、23 の七つの基底を使い、それらは 64 ビット整数すべて、ひいては約九千兆までの安全な JavaScript 整数すべてに十分です。

ごく小さな素数 2 と 3 は素数として短絡します。証人が n を割りかつ n より小さいとき、n は明らかな倍数なので、その証人が失敗基底として報告されます。乱数抽選も、壁時計の種も、ネットワーク表も、Date もありません。

固定基底の素数判定が役立つ場面

暗号の授業や CTF の指導者は、乱数証人の確率的検査と、応答内に保証上限を名指しする固定基底の証明書との違いを学生に示すために、決定的 Miller–Rabin 判定を使います。ライブラリ作者は、モジュラ冪のリファクタが判定を静かに反転させないよう、既知の素数・強い擬素数・合成数に対する単体テストを固定します。

アプリケーション開発者は、より長いパイプラインの前に素数形の設定値、パズルの種、玩具の Diffie–Hellman パラメータを検証し、計算機代数システムを立てずに偶数や小さな合成数を捕まえます。検索意図が固定証人と硬い上限を持つ決定的 Miller–Rabin アルゴリズムそのものであるときに本ツールを選んでください。

合成数の最小約数、完全な素因数分解、メルセンヌ数向け Lucas–Lehmer、自分で与えるカスタム証人リスト付きの確率的検査が必要なときではありません。

固定基底 Miller–Rabin 証明書の授業

素数または合成数の判定を正確な証人リストと保証上限とともに学生に示し、乱数証人の確率的検査との違いを具体的にします。

上限下での素数形パラメータ検証

固定基底 Miller–Rabin に落ちる設定値、パズルの種、玩具暗号の法を拒否し、失敗した証人を監査証跡に記録します。

決定的 Miller–Rabin 判定の料金は?

同じ検査はこのページのブラウザでも無料で動きます。無効な入力は課金されません。

どの数が受け付けられますか?

2 から公開保証上限 9007199254740991 までの整数全体です。

どの証人基底が使われますか?

固定リスト 2, 3, 5, 7, 11, 13, 23 です。

これは確率的 Miller–Rabin ですか?

いいえ。 基底は固定で、対応上限内のすべての整数に十分と証明されているため、同じ n は常に同じ決定的な素数または合成数の判定になります。

上限を超える数を入れるとどうなりますか?

上限の値を示したメッセージとともに受け付けられません。固定基底による判定が証明として成り立つのは9007199254740991までで、それを超えると同じ基底では合成数を見逃すおそれがあるからです。

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

POSThttps://api.kit.forhosting.com/numth/miller-rabin-deterministic

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

curl -X POST https://api.kit.forhosting.com/numth/miller-rabin-deterministic \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":97}'
{
  "n": 97
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.miller_rabin_deterministic",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_limitedリクエストが多すぎます。しばらく待ってから再度お試しください。

同じ純粋なモジュラ算術が無料のブラウザ経路と API 経路を支えるため、宿題チェック、暗号の玩具、自動化スクリプトが境界付近の Carmichael 数や強い擬素数で食い違うことはありません。

決定的 Miller–Rabin の返り値と上限の意味

成功した呼び出しは、固定基底の Miller–Rabin 一式の下で n が素数か、どの証人基底が使われたか、この一式が正しく決着すると保証する最大の整数は何か、そして n が合成数なら強いおそらく素数検査に最初に落ちた証人は何か、という四つの関連質問に答えます。固定証人リストは、その範囲内でのみ数学的証明書だからです。それより上では同じ基底でも合成数を見逃すことがあります。この硬い打ち切りは、戦略を静かに切り替えたり証明書の限界を述べずに素数だと主張したりし得る一般の素数判定器との製品上の違いです。応答は、真偽の prime フラグ、エコーされた整数 n、順序付きの witnesses 配列、数値の上限、witness_count、failing_witness フィールド(素数では null、合成数では具体的な基底)、クライアントがアルゴリズム経路を記録できるよう miller_rabin_deterministic に設定された method ラベルを持つコンパクトな JSON オブジェクトです。欠落・小数・非数値・厳密に 2 未満の入力は、モジュラ冪を実行する前に invalid_input で拒否されます。公開保証上限を超える値も invalid_input と上限を名指しするメッセージで拒否されます。契約は一つ、エラーメッセージは一式、固定された任意の n に対してバイト安定な JSON です。確率的な推測やすべての約数の完全因数分解ではなく、証人リストと上限が結果に書き込まれた監査可能な決定的 Miller–Rabin 判定が必要なときに、このエンドポイントを使ってください。

固定基底の強いおそらく素数検査の仕組み

偶数の合成数はフルループを回さず failing_witness を 2 として即座に拒否されます。

決定的 Miller–Rabin API が役立つ場面

データ技術者は素数だと主張する数値列をゲートし、行が失敗したとき監査ログに failing_witness フィールドを残します。能力は tier A なので、このページに数を貼り付けてブラウザで同じ論理を無料実行でき、スクリプトや SDK にタスクを配線するときは後から 1 リクエストあたり $0.002 で同じ契約を自動化できます。公開上限内で n を少なくとも 2 の整数に保ち、invalid_input は再試行ではなくクライアント側の修正として扱い、何を検査したかの再現可能な証明書が必要なときは常に witnesses と bound を記録してください。

モジュラ素数判定コードの単体テスト固定

暗号や数論ライブラリの変更を出荷する前に、安定した決定的 Miller–Rabin オラクルに対してゴールデン素数・合成数・上限外拒否をアサートします。

n が上限より大きいとどうなりますか?

タスクは invalid_input と保証上限を名指しするメッセージで失敗します。固定基底が認証された範囲の外では、決定的判定を主張しません。

KITの完全なドキュメントを見る →