現代暗号理論
1.どんな自然数も素数の積で表すことができる(素因数分解)。そして素因数分解の方法は一通り(素因数分解の一意性or算術の基本定理)。素因数分解は非常に難しい
例えば,13297×96479=1282881263 という等式を考える。左辺だけ与えられたとき右辺を計算するのは簡単だが,右辺が与えられたときに左辺のように分解を与えるのは非常に難し。
2.例えば 100桁 の数を素因数分解するのはコンピュータを使っても天文学的な時間がかかる。50桁の数どうしのかけ算なら簡単だ。現代の暗号(の一部)は素因数分解の難しさに基づいている。大きい数(300桁程度)を公開しておき,その素因数分解を知っている人だけが暗号文を復号できるような構造になっている。RSA暗号の仕組みと安全性という。
3.素因数分解が難しい(多項式時間で解けない)ことは多くの人に信じられている(証明されてはいない)が,与えられた数が素数かどうか判定するだけなら多項式時間で解くことができる。多項式時間についてはP≠NP予想の主張の解説を参照にする。より単純で理解しやすいフェルマーテストという確率的な素数判定法がある。
*RSA:Rivest,Shamir,Adelman