素数判定ツール
ある数が素数かどうかを判定し、その理由を正確に表示します：中小の数値には √n までの実際の試し割り法を、暗号レベルの巨大数には本物のミラー–ラビンテストの詳細な手順を示します。
🔒 ブラウザ内で完全に処理されます。ここに入力した内容はアップロードされません。
結果
この素数判定ツールは、ある整数が素数かどうかを判定するだけでなく、ほとんどのオンライン計算機とは異なり、キャッシュされたルックアップテーブルではなく、それを証明した実際のアルゴリズムを表示します。正負や大小を問わず任意の整数を入力すると、ツールがそのサイズに基づいて実行する実際のアルゴリズムを選択します。
10¹²（1兆）未満の数値に対しては、実際の試し割り法を実行します：2から始めて、√n の切り捨て値までのすべての整数を約数候補として試し、いずれかが割り切れれば合成数、√nまでのすべての候補で割り切れなければ素数と確認します。候補数が膨大な場合、表示されるトレースは最初の約18個と最後の候補に絞られ、途中でスキップされた候補数が正直に注記されます——しかし、実際の計算ではすべての候補がチェックされており、計算上スキップされる候補はありません。
この閾値以上の数値（暗号で使われるサイズ域）では、試し割り法では時間がかかりすぎるため、固定された決定論的な13個の素数の witness（2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41）を用いたミラー–ラビン素数判定法に切り替えます。この witness セットはよく知られた結果であり、3,317,044,064,679,887,385,961,981（約3.3×10²⁴）未満のすべての n に対して偽陽性がないことが計算検証によって確立されています（Sorenson & Webster, 2015 およびその決定論的 witness テーブルを参照）。この範囲を超える数値に対しても同じテストが実行されますが、数学的確実性ではなく、極めて強力な確率的保証となることをツールは正直に表示します。
ミラー–ラビンテストのトレースでは、n − 1 = 2ˢ × d（dは奇数）と書き下し、実際の BigInt によるべき乗剰余計算——バイナリ法を用い、数値が爆発しないよう毎ステップで n で剰余を取る——を1つ目の witness についてビット単位で実行し、各 witness の判定結果（合成数の場合、どの witness が合成性を証明したかを含む）を報告します。すべての処理はブラウザ上でローカルに実行され、サーバーや外部APIは使用せず、データがデバイスの外に出ることは一切ありません。