素因数分解の難しさと素数判定

• 2以上の整数は，素数の積で表すことができます（素因数分解）。そして素因数分解の方法は一通りです（素因数分解の一意性・算術の基本定理）。

• 素因数分解は非常に難しい
  例えば，$13297×96479=1282881263$ という等式を考えてみます。左辺だけ与えられたとき右辺を計算するのは簡単ですが，右辺が与えられたときに左辺のように分解するのは非常に難しそうです。
  これくらいの数字なら現代のコンピュータを使えば一瞬ですが，例えば $100$ 桁の数を素因数分解するのは，コンピュータを使っても天文学的な時間がかかると考えられています（50桁の数どうしのかけ算なら簡単）。

• 現代の暗号（の一部）は素因数分解の難しさに基づいている
  大きい数（300桁程度）を公開しておき，その素因数分解を知っている人だけが暗号文を復号できるような仕組みがあります。→RSA暗号の仕組みと安全性

素因数分解が難しい（多項式時間で解けない）ことは多くの人に信じられています（証明されてはいない）が，与えられた数が素数かどうか判定するだけなら多項式時間で解けます。

多項式時間についてはP≠NP予想の主張の解説を参照してください。

以下では，より単純で理解しやすいフェルマーテストという確率的な素数判定法について解説します。

フェルマーの小定理の対偶から以下の定理が成立します：

この定理を用いて，与えられた数 $n$ が素数かどうかを高確率で判定できます！

例示のため小さい数で計算しましたが，$a,n$ が大きい数でも合同式の性質を用いれば $a^n\bmod{n}$ を計算することは比較的容易なのでこの判定は高速です。

実際，ほとんどの合成数 $n$ と自然数 $a$ に対して $a^n\not\equiv a\pmod{n}$ が成立することが知られているので，いくつかの $a$ に対して $a^n\equiv a\pmod{n}$ が成立すれば $n$ は非常に高い確率で素数です。

しかし，残念ながら100％素数であるとは言えないのです。合成数なのにフェルマーテストでは素数のように振る舞ってしまういやなやつをフェルマー擬素数と言います。

Tag:素数にまつわる覚えておくべき性質まとめ