2014/07/23

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

分野: 整数問題  レベル: 最難関大学

素数について,理系なら知っておくべき知識について整理しました。

素因数分解の難しさ

・どんな自然数も素数の積で表すことができます(素因数分解)。そして素因数分解の方法は一通りです(素因数分解の一意性or算術の基本定理)。

・素因数分解は非常に難しい
例えば,$13297×96479=1282881263$
という等式を考えてみます。左辺だけ与えられたとき右辺を計算するのは簡単ですが,右辺が与えられたときに左辺のように分解を与えるのは非常に難しそうです。

これくらいの数字なら現代のコンピュータを使えば一瞬ですが,例えば $100桁$の数を素因数分解するのはコンピュータを使っても天文学的な時間がかかると考えられています。(50桁の数どうしのかけ算なら簡単)

・現代の暗号(の一部)は素因数分解の難しさに基づいている。(この事実は教養として知っておきましょう!)

大きい数(300桁程度)を公開しておき,その素因数分解を知っている人だけが暗号文を復号できるような構造になっています。→RSA暗号の仕組みと安全性

素数判定問題

素因数分解が難しい(多項式時間で解けない)ことは多くの人に信じられています(証明されてはいない)が,与えられた数が素数かどうか判定するだけなら多項式時間で解くことができます。
多項式時間についてはP≠NP予想の主張の解説を参照してください。

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

フェルマーテスト

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

定理:ある自然数 $a$ が存在して
$a^{n}\not\equiv a \:\mathrm{mod}\:n$
が成り立てば $n$ は合成数。

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

例1

$4$ は合成数
$a=2$ としてみると,$2^4=16\not\equiv 2\:\mathrm{mod}\:4$

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

例2

$7$ は素数っぽい
$a=2$ としてみると $2^7=128\equiv 2\:\mathrm{mod}\:7$
$a=3$ としてみると $3^7=3\cdot 9^3\equiv3\cdot2^3\equiv 3\:\mathrm{mod}\:7$
この結果から $7$ が素数っぽいことが予想できます。

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

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

素数の話題は数学の中でもとりわけ深遠で危険な香りがする分野です

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

分野: 整数問題  レベル: 最難関大学