## 定義 素数(prime)は、1より大きく、自分自身と1以外に約数を持たない数と定義される。0, 1, −1 のみが素数でも合成数(composite)でもない特殊な整数として扱われる。素数の分布は整数列の中で不規則(erratic)に見えるが、その密度には厳密な極限則が成り立つ。π(n)(n 以下の素数の個数)について、素数定理(Prime Number Theorem)は極限 lim_{n→∞} π(n)/(n/ln n) = 1 を主張する。この定理は Legendre が1798年に予想し、一世紀後の1896年に de la Vallée Poussin と Hadamard が証明したが、Gauss が1791年、15歳のときの手稿に同じ予想を記していたことが死後に発見されている。素数定理自体の証明は高度だが、本章では弱い形である Chebyshev の定理(π(n) > n/(3 ln n)、n > 1)が扱われ、この評価だけで章内の応用には十分とされる。素数に関する未解決問題として、双子素数予想(p と p + 2 がともに素数であるような p が無限に存在するという予想。1966年に Chen が「p + 2 が高々2個の素数の積である p が無限に存在する」ことを示し、ほぼ真であることが知られている)、Goldbach 予想(2より大きいすべての偶数は2つの素数の和として表せるという予想。1939年に Schnirelman が「すべての偶数は高々30万個の素数の和として表せる」ことを示し、現在では高々6個まで改善されている)、そして**素因数分解の効率的アルゴリズムの不在についての予想**(2つの大きな素数の積 n = pq が与えられたとき、p, q を n のビット長の多項式時間で復元する手続きは存在しないという未証明の予想。現時点で知られる最良のアルゴリズムは数体篩法 <number field sieve> で、n が300桁以上になると事実上不可能になる)が挙げられる。この最後の予想が RSA 公開鍵暗号方式の安全性の根拠となる。素数のもう1つの中心的な性質が**算術の基本定理(Fundamental Theorem of Arithmetic、Unique Factorization Theorem とも呼ばれる)**で、すべての正整数は弱減少な(重複を許す)素数列の積として一意に表せるという主張である。証明の鍵となるのが「p が素数で p | ab ならば p | a または p | b」という補題で、この補題は一意分解を仮定せずに、gcd と整数線形結合の性質だけから証明され(循環論法を避けるための重要な工夫)、証明全体は整列原理(Well Ordering Principle)を用いた背理法で完成する。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]], ch.8 §8.3〜§8.4) ## 横断的知見 （この概念に触れたソースは現時点で本章のみ。2ソース目以降の ingest で突き合わせが可能になり次第、ここに観察を追記する。） ## 未解決の問い - 素因数分解の効率的アルゴリズムが存在しないという予想は RSA の安全性の根拠だが、本章はこれが未証明であることを繰り返し強調するにとどまる。量子計算機による Shor のアルゴリズム(素因数分解を多項式時間で解く)との関係は本章では扱われていない。[[公開鍵暗号方式]] concept の既存内容(Security Engineering 3e 由来)は Shor のアルゴリズムに言及しているため、本章の素因数分解困難性予想と量子計算機の脅威の関係を、両ソースを突き合わせて次回整理する余地がある。 - AKS 素数判定法(2002年、Agrawal・Kayal・Saxena による多項式時間の決定的素数判定アルゴリズム)は本章の囲み記事(text box)で紹介されるが、次数12(後に5まで改善)の多項式では実用上は確率的素数判定法(Strassen の方法、1974年)に及ばないとされる。実務での素数判定アルゴリズムの選択基準を扱う他ソースとの突き合わせが未着手。 ## 関連 - [[@2015__MIT__Mathematics for Computer Science - Chapter 8 Number Theory]] — 素数の性質・算術の基本定理・素数定理 - [[最大公約数]] — 算術の基本定理の証明で gcd と線形結合の性質が使われる - [[合同算術]] — 素数 p では Euler の φ 関数が φ(p) = p − 1 になる - [[公開鍵暗号方式]] — 素因数分解の困難性が RSA の安全性の根拠 ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 8, §8.3〜§8.4.