AKS素数判定法 （-そすうはんていほう）は、与えられた自然数 が素数 であるかどうかを決定的 多項式時間 で判定できる、世界初のアルゴリズム である。ここで、素数判定法が多項式時間であるとは、与えられた自然数
n
{\displaystyle n}
log
(
n
)
{\displaystyle \log(n)}
多項式 を上界 とすることをいう。
n
{\displaystyle n}
AKS素数判定法は2002年 8月6日 に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学 のマニンドラ・アグラワル 教授と、2人の学生ニラジュ・カヤル 、ナイティン・サクセナ （Nitin Saxena）の3人の名前から付けられた。
この素数判定法が発見される以前にも、素数の判定方法 は多数知られていたが、リーマン予想 などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。
素数判定という重要な問題が実際にクラスP に属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解 した方がよい）。
AKS素数判定法は、ある意味ではフェルマーテスト の改良と見ることができる。
フェルマーの小定理 の対偶 である次のような命題を考える。
a
{\displaystyle a}
n
{\displaystyle n}
互いに素 な自然数 であるとする。
a
n
≢
a
(
mod
n
)
{\displaystyle a^{n}\ \not \equiv \ a{\pmod {n}}}
であるとき、
n
{\displaystyle n}
合成数 である。
フェルマーテストはこの十分条件によって確率的素数判定 を行うものであったが、上は必要条件ではないので、合成数であるにもかかわらずそれを検出できない場合があった。特に、カーマイケル数 と呼ばれる合成数が無限個存在し、これらはいかなる
a
{\displaystyle a}
そこで、この条件を次のように改良する。
a
{\displaystyle a}
n
{\displaystyle n}
(
X
+
a
)
n
≢
X
n
+
a
(
mod
n
)
{\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {n}}}
のとき、かつそのときに限り、(iff:if and only if)
n
{\displaystyle n}
このことは、二項定理 により各次数の係数を評価すれば容易に証明できる。
上の式は、
X
{\displaystyle X}
厳密にしたことによりフェルマーテストとは異なり必要十分条件を与えている。したがって上の合同式を真面目に評価してやれば素数性を判定する決定性アルゴリズムができるが、これは時間がかかりすぎる。つまり、最悪の場合
n
{\displaystyle n}
n
{\displaystyle n}
指数関数時間 である。
そこでもう少し大雑把に評価することにする。具体的には、何らかの小さい
r
{\displaystyle r}
X
r
−
1
{\displaystyle X^{r}-1}
X
r
−
1
{\displaystyle X^{r}-1}
高々
r
−
1
{\displaystyle r-1}
(
X
+
a
)
n
≢
X
n
+
a
(
mod
X
r
−
1
,
n
)
{\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {X^{r}-1,n}}}
しかし、これは「大雑把な評価」である。評価を楽にした分、その精度も落ちている。このままでは、合成数なのに誤って素数であると判定してしまう恐れがある。そこで、パラメータ
a
{\displaystyle a}
a
{\displaystyle a}
この発想が、AKSアルゴリズムの肝である。つまり、十分にたくさんの
a
{\displaystyle a}
X
r
−
1
{\displaystyle X^{r}-1}
a
{\displaystyle a}
r
{\displaystyle r}
n
{\displaystyle n}
アルゴリズム [ 編集 ] 素数性を判定すべき、2以上の自然数
n
{\displaystyle n}
もし、
n
{\displaystyle n}
累乗数 であるならば「合成数である」と出力してアルゴリズムを終了する。
o
r
(
n
)
>
4
log
2
n
{\displaystyle o_{r}(n)>4\log ^{2}n}
r
{\displaystyle r}
もし、ある
a
≤
r
{\displaystyle a\leq r}
1
<
(
a
,
n
)
<
n
{\displaystyle 1<(a,n)<n}
もし、
n
≤
r
{\displaystyle n\leq r}
1
{\displaystyle 1}
[
2
ϕ
(
r
)
log
n
]
{\displaystyle [2{\sqrt {\phi (r)}}\log n]}
a
{\displaystyle a}
(
X
+
a
)
n
≢
X
n
+
a
(
mod
X
r
−
1
,
n
)
{\displaystyle (X+a)^{n}\ \not \equiv \ X^{n}+a{\pmod {X^{r}-1,n}}}
「素数である」と出力してアルゴリズムを終了する。
ただし、上において、
(
a
,
b
)
{\displaystyle (a,b)}
a
{\displaystyle a}
b
{\displaystyle b}
最大公約数
o
r
(
n
)
{\displaystyle o_{r}(n)}
r
{\displaystyle r}
n
{\displaystyle n}
位数 、つまり
n
e
≡
1
(
mod
r
)
{\displaystyle n^{e}\equiv 1{\pmod {r}}}
e
{\displaystyle e}
[
x
]
{\displaystyle [x]}
ガウス記号
ϕ
{\displaystyle \phi }
オイラーのφ関数
第5ステップで用いている判定法は、累乗数についてはうまく働かない。累乗数であるならばすなわち合成数なのだから、最初のステップにおいて累乗数であると判明した場合には「合成数である」と出力して終了する。
次に、
n
{\displaystyle n}
r
{\displaystyle r}
r
{\displaystyle r}
最小公倍数 に関する議論から
r
≤
⌈
16
log
(
n
)
5
⌉
{\displaystyle r\leq \lceil 16\log(n)^{5}\rceil }
その次に、
n
{\displaystyle n}
(
Z
/
r
Z
)
×
{\displaystyle (\mathbb {Z} /r\mathbb {Z} )^{\times }}
元 であるかを確かめている。これは第5ステップが正しく動作するために必要である。
(
Z
/
r
Z
)
×
{\displaystyle (\mathbb {Z} /r\mathbb {Z} )^{\times }}
n , r ) = 1 であるが、この段階で最大公約数が 1 でなかったなら、それはつまり
n
{\displaystyle n}
第4ステップでは、もしこの段階で
n
≤
r
{\displaystyle n\leq r}
n
{\displaystyle n}
n
−
1
{\displaystyle n-1}
n
{\displaystyle n}
n
{\displaystyle n}
第5ステップは、アルゴリズムの中心的な部分である。ここでいずれかの
a
{\displaystyle a}
n
{\displaystyle n}
第5ステップにおいて、十分に多くの
a
{\displaystyle a}
n
{\displaystyle n}
PRIMES is in P の半ばはその証明に費やされている。
時間的計算量 [ 編集 ] AKSアルゴリズムの時間的計算量は高々
O
~
(
log
(
n
)
7.5
)
{\displaystyle {\tilde {O}}(\log(n)^{7.5})}
PRIMES is in P の初版では、このアルゴリズムは
O
~
(
log
(
n
)
12
)
{\displaystyle {\tilde {O}}(\log(n)^{12})}
O
~
(
log
(
n
)
7.5
)
{\displaystyle {\tilde {O}}(\log(n)^{7.5})}
O
~
(
log
(
n
)
6
)
{\displaystyle {\tilde {O}}(\log(n)^{6})}
篩理論 の高度な結果によっているが、初歩的な代数学 の知識だけでも
O
~
(
log
(
n
)
10.5
)
{\displaystyle {\tilde {O}}(\log(n)^{10.5})}
ただし、記法
O
~
{\displaystyle {\tilde {O}}}
f
(
x
)
=
O
~
(
g
(
x
)
)
⇔
f
(
x
)
=
O
(
g
(
x
)
⋅
P
o
l
y
(
log
g
(
x
)
)
)
{\displaystyle f(x)={\tilde {O}}(g(x))\Leftrightarrow f(x)=O(g(x)\cdot \mathrm {Poly} (\log g(x)))}
即ち、記号
O
~
{\displaystyle {\tilde {O}}}
ランダウの記号 O を少しだけ弱めたものである。
f
(
x
)
=
O
~
(
g
(
x
)
)
{\displaystyle f(x)={\tilde {O}}(g(x))}
ϵ
>
0
{\displaystyle \epsilon >0}
f
(
x
)
=
O
(
g
(
x
)
1
+
ϵ
)
{\displaystyle f(x)=O\left(g(x)^{1+\epsilon }\right)}
各ステップの評価 [ 編集 ]
p進 のニュートン法 を用いれば、各自然数
b
{\displaystyle b}
n
b
{\displaystyle {\sqrt[{b}]{n}}}
O
~
(
log
(
n
)
2
)
{\displaystyle {\tilde {O}}(\log(n)^{2})}
n
=
a
b
{\displaystyle n=a^{b}}
b
{\displaystyle b}
log
2
n
{\displaystyle \log _{2}n}
O
~
(
log
(
n
)
3
)
{\displaystyle {\tilde {O}}(\log(n)^{3})}
第2ステップは、
r
≤
⌈
16
log
(
n
)
5
⌉
{\displaystyle r\leq \lceil 16\log(n)^{5}\rceil }
O
~
(
log
(
n
)
7
)
{\displaystyle {\tilde {O}}(\log(n)^{7})}
第3ステップでは、ユークリッドの互除法 を用いれば最大公約数 1 つを
O
~
(
log
(
n
)
)
{\displaystyle {\tilde {O}}(\log(n))}
O
(
r
)
=
O
(
log
(
n
)
5
)
{\displaystyle O(r)=O(\log(n)^{5})}
O
~
(
log
(
n
)
6
)
{\displaystyle {\tilde {O}}(\log(n)^{6})}
第4ステップは、単に比較するだけであるから
O
(
log
n
)
{\displaystyle O(\log n)}
第5ステップでは、
mod
X
r
−
1
{\displaystyle \mod X^{r}-1}
r
−
1
{\displaystyle r-1}
mod
n
{\displaystyle \mod n}
n
−
1
{\displaystyle n-1}
高速フーリエ変換 を用いれば、このような多項式の冪 は
O
~
(
r
log
(
n
)
2
)
{\displaystyle {\tilde {O}}(r\log(n)^{2})}
O
~
(
r
ϕ
(
r
)
log
(
n
)
3
)
=
O
~
(
log
(
n
)
10.5
)
{\displaystyle {\tilde {O}}(r{\sqrt {\phi (r)}}\log(n)^{3})={\tilde {O}}(\log(n)^{10.5})}
第6ステップは、定数時間 である。
したがって、全体の時間は
O
~
(
log
(
n
)
10.5
)
{\displaystyle {\tilde {O}}(\log(n)^{10.5})}
評価の改良 [ 編集 ] 全体の時間を支配しているのは、第5ステップの時間であり、ひいては
r
{\displaystyle r}
r
{\displaystyle r}
⌈
16
log
(
n
)
5
⌉
{\displaystyle \lceil 16\log(n)^{5}\rceil }
篩理論より
r
=
O
(
log
(
n
)
3
)
{\displaystyle r=O(\log(n)^{3})}
O
~
(
log
(
n
)
7.5
)
{\displaystyle {\tilde {O}}(\log(n)^{7.5})}
更に、いくつかの証明されていない仮説を認めるならば、
r
{\displaystyle r}
アルチン予想 を認めるならば
r
=
O
(
log
(
n
)
2
)
{\displaystyle r=O(\log(n)^{2})}
ソフィー・ジェルマン素数 の密度予想が正しいと仮定すれば、
r
=
O
~
(
log
(
n
)
2
)
{\displaystyle r={\tilde {O}}(\log(n)^{2})}
これらの仮説はともに一般リーマン仮説 を認めれば証明できる。多くの数学者 がリーマン仮説は正しいと信じていることを考えれば、
r
=
O
(
log
(
n
)
2
)
{\displaystyle r=O(\log(n)^{2})}
O
~
(
log
(
n
)
6
)
{\displaystyle {\tilde {O}}(\log(n)^{6})}
関連項目 [ 編集 ] 外部リンク [ 編集 ] 
![[2\sqrt{\phi(r)} \log n]](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf2ade60c5026403ac67f0366cf4f91d563e04cb)
![[x]](https://wikimedia.org/api/rest_v1/media/math/render/svg/07548563c21e128890501e14eb7c80ee2d6fda4d)
![\sqrt[b]{n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/988fbf12d791c55140f813e0e2a16686d28a34e9)
