素数判定機（無料）- 1000桁まで対応・素因数分解も

余談ですが ― 素数はなぜ重要なのか

素数はしばしば「数の原子」と呼ばれます。算術の基本定理によれば、1 より大きいすべての整数は素数の積としてただ一通りに表せます。つまり素数は、あらゆる整数を組み立てるための、それ以上分解できない部品ということです。上に表示される素因数分解が一意である理由もここにあり、360 は 2³ × 3² × 5 であって、それ以外の書き方はありません。

巨大な数が素数かどうかを「判定する」ことと「素因数分解する」ことは別の問題で、その違いの歴史は知っておくと面白いです。フェルマーの小定理を使えば高速な判定ができますが、どの底を使っても通り抜けてしまう合成数が存在します。その最小の例が 561 で、上のボタンから試せます（このような数をカーマイケル数といいます）。ミラー・ラビン法は途中で 1 の平方根を確認することでこの抜け穴をふさぎ、最初の 13 個の素数を底に使えば、約 3.3 × 10²⁴ 未満のすべての数に対して決定的な判定法になることが証明されています。それを超える範囲では、このページは強リュカ法を追加した Baillie–PSW 法を使います。この判定を通過する合成数はまだ 1 つも見つかっていませんが、証明はされていないため、非常に大きな数の結果は「確率的素数」と表示しています。

この「判定は簡単なのに分解は難しい」という非対称性が、現代の暗号技術を成り立たせています。HTTPS 通信や電子署名をいまも支える RSA 暗号は、大きな素数 2 つを掛け合わせて公開鍵を作ります。その積から元の素数を取り出すことは事実上不可能だと考えられているため、検証は一瞬でできるのに、分解はできないという状態が作れるわけです。このページでもその差を体感できます。1000 桁の数の素数判定はほぼ瞬時に終わりますが、30 桁の素数 2 つを掛けた 60 桁の合成数は、素因数分解しきれずに終わります。

素数には、数学で最も古くから残る未解決問題もあります。11 と 13、あるいは 1,000,000,000,061 と 1,000,000,000,063 のような双子素数が無限に存在するかどうかは、いまだに誰も知りません。素数そのものが尽きないことは紀元前 300 年頃にユークリッドが証明しているのに、です。記録更新の探索も続いています。GIMPS プロジェクトの参加者たちは 2^p − 1 という形のメルセンヌ数を手分けして調べており、現在知られている最大の素数は 2024 年に見つかった 2¹³⁶²⁷⁹⁸⁴¹ − 1 で、41,024,320 桁もあります。