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

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

## 素数判定問題

$n$ bit $(n ≥ 2)$ の整数 $x$ が与えられる。$x$ が素数であるか判定せよ。

## 素数判定問題は co-NP

$x$ が素数でない証拠が与えられたとき、$n$ の多項式時間で $x$ が素数でないことを検証することができるならば、素数判定問題は co-NP に属すると言います。

例えば、以下のようにすれば、多項式時間で $x$ が素数でないことを検証することができます。

:::info

証拠 : $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$ が素数であることを検証するため、[原始根](https://manabitimes.jp/math/842) を用います。

:::warning

整数 $1 ≤ a < x$ に対し、$a^0, a^1, a^2, \dots\pmod{x}$ は周期的である。([オイラーの定理](https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%AE%9A%E7%90%86_(%E6%95%B0%E8%AB%96)))
$x$ が素数であるとき、ある整数 (原始根) $1 ≤ a < x$ が存在して、$a^0, a^1, a^2, \dots\pmod{x}$ の周期は $x-1$ である。
$x$ が合成数であるとき、どんな整数 $1 ≤ a < x$ に対しても、$a^0, a^1, a^2, \dots\pmod{x}$ の周期は $x-1$ より小さい。

:::

$1$ から始まって $1$ に帰ってくるまでが $1$ 周期となるので、原始根 $a$ を証拠として、以下を検証すれば良いです。

:::info

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

:::

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

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

:::info

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

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

#### 検証アルゴリズム

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

:::

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

まず、再帰部分以外が多項式時間であることを確認します。
$n$ bit の掛け算が $O(n^2)$ 時間であり、$k ≤ 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%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95