本記事は機械翻訳によるものであり、原文は英語です。 原文を読む
素数は数式で表せる割合で疎になっていく
1024 ビットの数の近くでは、355 個の奇数のうち 1 個が素数です。これは決して小さな確率ではなく、これこそが公開鍵暗号を実現可能にしている唯一の理由です。
100 未満の素数は 25 個、1000 未満では 168 個、100 万未満では 78,498 個存在します。個数は減っていきますが、決して途絶えることはなく、それらが疎になっていく割合は数学において最も有用な事実の 1 つです。
ln n 個に 1 個
ある数 n の近くでは、およそ ln n 個に 1 個の割合で素数が存在します。100 未満では、この予測により 100 / ln 100 = 21.7 個の素数があると示され、Prime Sieve は実際の個数である 25 の隣にまさにその値を、13.1% の誤差とともに表示します。
ここでの見積もりは粗いものですが、次第に改善していきます。100 万の時点では、N / ln N は実際の 78,498 個に対して 72,382 という値を与え、誤差は 7.8% となります。N が大きくなるにつれて相対誤差は小さくなりますが、これこそが素数定理の示すまさにその内容です。
一見悪く見える、より優れた推定
このツールは 2 つ目の近似式として、対数積分である Li(N) も出力します。N = 100 のとき、これは 29.1 という値を与えますが、これは粗い見積もりの 13.1% に対して 16.3% の誤差であり、より悪い結果となっています。
その行だけを見た人は、より複雑な公式を使う価値がないと結論付けるかもしれません。しかし N の値を変更すると、順位は逆転し、二度と元に戻ることはありません。
- N = 100: N/lnN の誤差 13.1%、Li の誤差 16.3%
- N = 1000: N/lnN の誤差 13.8%、Li の誤差 5.1%
- N = 10⁶: N/lnN の誤差 7.8%、Li の誤差 0.16%
Li は N / ln N の改良版というより、その本質的な姿です。粗い公式は、2 付近の密度と 100 万付近の密度が大きく異なるにもかかわらず、n における密度を 0 から n までの全範囲に適用してしまっています。Li は密度を一定とみなす代わりに、範囲全体にわたって 1/ln t を積分します。その結果、近道の公式ではいまだに 8% の誤差が生じるのに対し、誤差を 600 分の 1 にまで小さくできるという見返りが得られます。
ある近似式を 1 回評価しただけでは、それが優れているかどうかは分かりません。入力が大きくなるにつれたときの挙動を確認する必要があります。
なぜ素数は決して尽きないのか
それは 1/ln n の減少が緩やかだからです。その和は発散するため、素数は疎ではあっても有限にとどまるほど疎ではないのです。
ユークリッドによる証明は、より直接的であり、さらに古いものです。任意の有限の素数リストをとり、それらをすべて掛け合わせて 1 を加えます。得られた結果をリスト内のどの素数で割っても余りは 1 になるため、その素因数はすべてリストの中には存在しないことになります。したがって、どのような有限のリストも完全なものとはなり得ません。
このツールの他の 2 つの表示項目は、いまだにどれほどの問題が未解決であるかを示しています。100 未満における 8 組の双子素数を数え上げ、最大の間隔を 8 と報告します。双子素数が無限に続くかどうかは未証明であり、連続する平方数の間に常に素数が存在するのかという予想も同様に未証明です。
鍵の長さを決定づける数
RSA 鍵の生成とは大きな素数を見つけることを意味し、その手法は適切なサイズの奇数をランダムに選び出し、それをテストすることです。
それに要する時間は、まさに密度の問題に帰着します。1024 ビットの数は 2¹⁰²⁴ の近くにあり、ln(2¹⁰²⁴) = 1024 × ln 2 = 710 となります。したがって、その付近ではおよそ 710 個に 1 個の数が素数であり、テスト対象を奇数候補のみに絞るため、355 個に 1 個の割合となります。
355 回の試行、そのそれぞれが高速な確率的素数判定です。これこそが鍵生成が地質学的な年月ではなく一瞬で完了する理由であり、そのすべてのスケール感は対数に由来しています。指数を増やしても、計算コストはビット長に対して線形に増加するだけであるため、2048 ビットや 4096 ビットの鍵が引き続き実用性を保っているのです。
仮に素数がほんの少しでも速く、例えば 1/n に従って疎になっていたとしたら、探索は絶望的となり、インターネットは別の仕組みの上に構築されていたことでしょう。
使用する素数を厳密に証明する人はいない
ある 1 つの詳細が 355 回の試行を低コストにしています。それは、このテストが素数性を確定的に証明するものではないという点です。
ミラー・ラビン素数判定法はランダムな証拠を選択し、すべての素数が同じ応答を返す質問を投げかけます。合成数が素数であるかのように応答することもありますが、それが可能となる証拠は全体の高々 4 分の 1 です。そのため、独立したラウンドを重ねるごとに誤判定の確率は少なくとも 4 分の 1 に減少します。40 ラウンドを行った場合、最悪のケースでも確率は 4⁻⁴⁰ 未満となり、これはおよそ 10⁻²⁴ に相当します。
この数値は、計算を行うマシン内で検出されないメモリエラーが発生する確率よりもはるかに低いものです。世界中の通信を保護している鍵は、ほぼ確実に素数である数値に基づいており、残された疑いの確率はハードウェアに起因する確率よりも小さいのです。