素数チェッカー

素数チェッカーは、整数が素数かどうかを示し、オンラインのほとんどの計算機とは異なり、キャッシュされたルックアップ テーブルではなく、それを証明した実際のアルゴリズムを表示します。正または負、小さいまたは巨大な整数を入力すると、ツールはそのサイズに基づいて実際にどのアルゴリズムを実行するかを決定します。

10¹² (1 兆) 未満の数値の場合は、本物の試行除算を実行します。2 から始まり、√n の下限までのすべての整数候補を可能な除数として試行し、均等に除算できた時点で停止するか (複合)、または √n までのすべての候補がチェックされた時点で何も除算が行われないことを確認します (素数)。候補数が膨大な場合、表示されるトレースは最初に試行された最大 18 件と最後の試行までに制限され、表示内でスキップされた数についての正直なメモが表示されます。ただし、すべての候補は実際にコードによってチェックされており、計算でスキップされるものはありません。

このしきい値 (暗号化で使用されるサイズの範囲) 以上の数値の場合、試行分割に時間がかかりすぎるため、ツールは 13 個の主要な証人 (2、3、5、7、11、13、17、19、23、29、31、37、41) の固定された決定論的なセットを使用した Miller-Rabin の素数性テストに切り替えます。この正確な証人セットはよく知られた結果です。3,317,044,064,679,887,385,961,981 (約 3.3×10²⁴) 未満の n には偽陽性がありません。これは、計算による検証によって確立された限界です (Sorenson & Webster、2015 年、およびこれが属する広く再現されている決定論的証人テーブルを参照)。その範囲を超えても同じテストが実行されますが、このツールは、保証が数学的な確実性ではなく、非常に強力な確率的な保証になることを正直に示します。

Miller-Rabin トレースは、n − 1 = 2ˢ × d を d が奇数で書き込み、次に実際の BigInt モジュラべき乗を実行し、数値が爆発しないようにすべての単一ステップで法 n を減少させる二乗と乗算を最初の証人に対して少しずつ実行し、数値が素数ではないことが判明した場合にどの証人が複合性を証明するかを含む各証人の評決を報告します。すべてがブラウザ内でローカルに実行されます。サーバーや外部 API はなく、データがデバイスから流出することはありません。