9.3 素数の謎

数論における最大と謎と洞察の一部は、素数の性質から得られる:

素数に関する有名な謎を三つ示す:

双子素数予想 (twin prime conjecture)

\(p\) と \(p + 2\) が両方とも素数であるような \(p\) は無限に存在する。

1966 年、Chenチェン は \(p\) と \(p + 2\) が二つ以下の素数の積であるような \(p\) が無限にあることを証明した。そのため、この予想はほぼ正しいことが知られている！

素因数分解の非効率性に関する予想

大きな二つの素数の積 \(n = pq\) が与えられたとき、\(n\) から素数 \(p\), \(q\) を復元する効率的なアルゴリズムは存在しない。つまり、\(n\) の二進表現の長さ (\(n\) 自体ではない) の多項式で押さえられるステップ数で \(p\) と \(q\) を見つけることが保証された多項式時間 (第 3.5 節) アルゴリズムは存在しない。\(n\) の二進表記の長さは最大で \(1 + \log_{2} n \) である。

現在知られている最良のアルゴリズムは数体篩法 (number field sieve) と呼ばれ、実行には次の値に比例した時間がかかる:

\[ \large e^{1.9 (\ln n)^{1/3}(\ln \ln n)^{2/3}} \]

この値は任意の \(\log n\) に関する多項式より速く大きくなり、\(n\) が \(300\) 桁以上のときは実用不可能になる。本章でこれから見るように、効率的な素因数分解は情報科学で特に重要な未解決問題である。

Goldbachゴールドバッハ の予想 (Goldbach's conjecture)

\(4\) 以上の任意の偶数は二つの素数の和である。

この予想 (予想 1.1.6) には本書でも何度か触れてきた。例えば \(4 = 2 + 2\), \(6 = 3 + 3\), \(8 = 3 + 5\) などが成り立つ。

1933 年、Schnirelmanシュニレルマン は全ての偶数は高々 \(21\) 個の素数の和だと示した。そこから研究が進み、現在では全ての偶数が最大で \(6\) 個の素数の和であることが知られている。

素数に規則性はあるだろうか？ 素数だけを並べると、その分布はランダムなように思える:

素数に関する最も重要な洞察の一つとして、整数と比較したときの素数の密度に正確な極限が存在することがある。具体的には次の通りである。まず、\(n\) 以下の素数の個数を \(\pi(n)\) とする:

例えば \(\pi(1) = 0\), \(\pi(2) = 1\), \(\pi(10) = 4\) が成り立つ。最後の等式は \(10\) 以下の素数が \(2\), \(3\), \(5\), \(7\) の \(4\) 個ある事実から分かる。\(\pi\) は \(1\) ずつ不規則に増加するものの、整数全体を見たときの増加速度は関数 \(n / \ln n\) で近似できることが知られている:

ここから、素数は次第に少なくなると分かる。大まかに言えば、整数 \(n\) 付近にある \(\ln n\) 個の整数につき \(1\) 個の素数が存在する。

素数定理は 1798 年に Legendreルジャンドル によって予想され、それから約一世紀後の 1896 年に deド laラ Valléeヴァレ Poussinプーサン と Hadamardアダマール によって証明された。しかし、1791 年に当時 15 才の Gaussガウス が同じ予想を記したと思われるノートが彼の死後に見つかっている (Gauss と同時代に生まれるという不幸に見舞われて「大数学者」になり損ねた人物たちには同情を禁じ得ない)。

素数定理の証明は本書の範囲を超えるものの、十分理解可能な証明を持った我々の用途には十分な結果が知られている: