素数判定が NP というはなし

参考資料 : https://www.cmi.ac.in/~ramprasad/lecturenotes/comp_numb_theory/lecture17.pdf

素数判定問題

$n$ bit

$(n\ge 2)$ の整数

$x$ が与えられる。

$x$ が素数であるか判定せよ。

素数判定問題は co-NP

$x$ が素数でない証拠が与えられたとき、

$n$ の多項式時間で

$x$ が素数でないことを検証することができるならば、素数判定問題は co-NP に属すると言います。

例えば、以下のようにすれば、多項式時間で

$x$ が素数でないことを検証することができます。

証拠 :

$2$ 以上の整数

$a,b$ であって、

$a\times b=x$ を満たすもの
検証アルゴリズム :

$a,b$ が

$2$ 以上であること、

$a\times b=x$ であることを確認する。

$n$ bit の掛け算は

$O(n\log n\log \log n)$ 時間とかでできるので、多項式時間です。

素数判定問題は NP

$x$ が素数である証拠が与えられたとき、

$n$ の多項式時間で

$x$ が素数であることを検証することができるならば、素数判定問題は NP に属すると言います。

多項式時間で

$x$ が素数であることを検証するため、原始根 を用います。

整数

$1\le a<x$ に対し、

$a^0,a^1,a^2,\dots (\mathrm{mod}x)$ は周期的である。(オイラーの定理)

$x$ が素数であるとき、ある整数 (原始根)

$1\le a<x$ が存在して、

$a^0,a^1,a^2,\dots (\mathrm{mod}x)$ の周期は

$x-1$ である。

$x$ が合成数であるとき、どんな整数

$1\le a<x$ に対しても、

$a^0,a^1,a^2,\dots (\mathrm{mod}x)$ の周期は

$x-1$ より小さい。

$1$ から始まって

$1$ に帰ってくるまでが

$1$ 周期となるので、原始根

$a$ を証拠として、以下を検証すれば良いです。

• $a^{x-1}=1(\mathrm{mod}x)$
  • これにより、周期が
    $x-1$ の約数であることがわかる
• $x-1$ の素因数分解を
  $x-1=p_1\times p_2\times \cdots \times p_k$ としたとき、各
  $p_i$ について、
  $a^{(x-1)/p_i}\ne 1(\mathrm{mod}x)$ である。

ここで、

$x-1$ の素因数分解は簡単に行えるものではないので、証拠に追加してこれを検証することにします。つまり、再帰的に素数であることの検証を行います。

まとめると、以下のようになります。

$x$ が素数であることの証拠

• 原始根
  $a$
• $x-1$ の素因数分解
  $x-1=p_1\times p_2\times \cdots \times p_k$
• 各
  $p_i$ が素数であることの証拠

検証アルゴリズム

• 各
  $p_i$ が素数であることを再帰的に検証
• $x-1=p_1\times p_2\times \cdots \times p_k$ であることを確認
• $a^{x-1}=1(\mathrm{mod}x)$ であることを確認
• 各
  $p_i$ に対し、
  $a^{(x-1)/p_i}\ne 1(\mathrm{mod}x)$ であることを確認

これが多項式時間であることを確認します。

まず、再帰部分以外が多項式時間であることを確認します。

$n$ bit の掛け算が

$O(n^2)$ 時間であり、

$k\le n$ であることから、再帰部分以外は

$O(n^4)$ 時間で抑えられます。

$x>2$ のとき、

$x-1$ は

$2$ で割れるので、再帰の深さは

$n$ 以下です。また、ある深さにおける

$n$ の合計が元々の

$n$ の定数倍で抑えられることから、再帰部分を含めても、全体で

$O(n^5)$ 時間となります。

素数判定問題は P

証拠が与えられなくても、

$n$ の多項式時間で

$x$ が素数であるかどうかを判定することができるならば、素数判定問題は P に属すると言います。

実は、素数判定問題は P に属することが知られています。

https://ja.wikipedia.org/wiki/AKS素数判定法