AKS素数判定法

同義語:AKS法Agrawal–Kayal–Saxenaの素数判定法AKS primality test

概要

AKS素数判定法(AKS primality test)とは、整数 $n>1$ が素数かどうかを、乱数も未証明の仮説も使わず、$\log n$ の多項式の時間で判定する Agrawal・Kayal・Saxena の算法である。$n$ が完全冪でなく、$n$ の位数が $\log^2 n$ を超える小さい $r$ について、$a\le\sqrt{\varphi(r)}\log n$ で $(X+a)^n\equiv X^n+a \pmod{X^r-1,n}$ を確かめる(小さい素因数は別に除く)。素朴な実装でも $O(\log^{16.5} n)$ のビット演算で済むので、素数判定はクラス $\mathrm{P}$ に入る。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 素数判定, Fermatの小定理, 有限体

AKS素数判定法(AKS primality test)は、与えられた整数 $n>1$ が素数かどうかを、乱数も未解決の仮説も使わず、$n$ の桁数の多項式の時間で判定する算法である。Agrawal・Kayal・Saxena が与えた。素数判定の問題が計算量のクラス P に入ることを初めて無条件に示した結果で、原論文の題は "PRIMES is in P" である。
出発点は、$a$ と $n$ が互いに素のとき、$n$ が素数であることと $(\mathbb Z/n\mathbb Z)[X]$ の中で $(X+a)^n=X^n+a$ が成り立つことが同値である、という事実である(素数判定 の命題「多項式の合同式による特徴づけ」)。このままでは左辺に $n$ 個の項があって遅い。そこで小さい $r$ を選び、$X^r-1$ を法として少数の $a$ についてだけ確かめる。すると情報は減るが、「$r$ を上手に選び、$a$ を十分多くとれば、合成数は通れない」ことが初等的な議論で証明できる。この記事では算法の正しさの完全な証明と、$r$ の大きさの評価を述べる。

内容扱い
算法の正しさ証明(thm-aks-main)
小さい $r$ の存在と大きさ証明(lem-aks-r)
多項式時間であること素朴な評価を証明(thm-aks-time)
高速な乗算を使った評価、Lenstra–Pomerance の改良主張と出典(rem-aks-improve)

算法

以下、$\log$ は底 $2$ の対数である。$\gcd(n,r)=1$ のとき、$n$ の $\mathbb Z/r\mathbb Z$ での乗法位数を $o_r(n)$ と書く。$f,g\in\mathbb Z[X]$ について、$f\equiv g\pmod{X^r-1,n}$ は環 $(\mathbb Z/n\mathbb Z)[X]/(X^r-1)$ で $f=g$ となることをいう。$\varphi$ は Eulerのφ関数 である。

AKS の算法

入力は整数 $n>1$ である。

  1. $n=a^b$($a,b\ge2$ は整数)と書けるなら、合成数と出力する。
  2. $\gcd(n,r)=1$ かつ $o_r(n)>\log^2n$ をみたす最小の正の整数 $r$ を求める。
  3. $1< \gcd(a,n)< n$ となる $a\le r$ があれば、合成数と出力する。
  4. $n\le r$ なら、素数と出力する。
  5. $a=1,2,\dots,\ell$($\ell:=\lfloor\sqrt{\varphi(r)}\log n\rfloor$)について、$(X+a)^n\not\equiv X^n+a\pmod{X^r-1,n}$ なら合成数と出力する。
  6. 素数と出力する。

AKS04 §4 の形である。段 5 の $(X+a)^n$ は、$X^r-1$ と $n$ で割った余りをとりながら繰り返し 2 乗で計算する。そのため係数は常に $r$ 個以下で、それぞれ $\log n$ ビット程度にとどまる。

AKS の定理

def-aks-algorithm は、$n$ が素数のときそのときに限り「素数」と出力する。

素数については簡単である。

素数が素数と判定されること

$n$ が素数なら段 1 と段 3 では止まらない。段 4 で止まらなければ、素数判定 の命題「多項式の合同式による特徴づけ」により $(\mathbb Z/n\mathbb Z)[X]$ の中で $(X+a)^n=X^n+a$ である($a\le\ell$ が $n$ と互いに素であることは下の評価 $\ell< r< n$ と $n$ が素数であることによる)。$X^r-1$ を法としてもこれは成り立つので、段 5 でも止まらず、段 6 で素数と出力する。

ここで段 2 の $r$ が存在し、しかも小さいことを確かめておく。$m$ 以下の正の整数の最小公倍数を $d_m$ と書く。

$r$ の大きさ

$n\ge2$ について、段 2 の $r$ は $r\le\max(3,\lceil\log^5n\rceil)$ をみたす。

積を割らない数を探す

$n=2$ なら $\log^2n=1$ で $o_3(2)=2$ なので $r=3$ である。$n\ge3$ とし、$B=\lceil\log^5n\rceil$、$L=\lfloor\log^2n\rfloor$ とおくと、$\log^53>10$ より $B\ge11$ である。
$$\Pi:=n^{\lfloor\log B\rfloor}\prod_{i=1}^L(n^i-1)$$
とおく。$\Pi< n^{\lfloor\log B\rfloor+L(L+1)/2}$ で、指数は $\log^4n$ 以下である。

指数の評価と $d_m$ の下界を開く

指数の評価。$u=\log^2n$ とする。$n=3$ では $B=11$、$L=2$ で、指数は $3+3=6\le u^2=6.31\cdots$ である。$n\ge4$ では $u\ge4$ で、$\lfloor\log B\rfloor+\frac12L(L+1)\le\log(u^{5/2}+1)+\frac12u^2+\frac12u$ である。$\log(u^{5/2}+1)\le\frac12u(u-1)$ は $u=4$ で $\log33< 6$ であり、$u\ge4$ で右辺の増え方のほうが速いので成り立つ。よって指数は $u^2$ 以下である。

$d_m$ の下界:$m\ge10$ なら $d_m\ge2^m$ である。$1\le j\le k$ について、ベータ積分を展開すると $\frac1{j\binom kj}=\int_0^1x^{j-1}(1-x)^{k-j}\,dx=\sum_{i=0}^{k-j}(-1)^i\binom{k-j}i\frac1{j+i}$ で、右辺に $d_k$ を掛けると整数なので、$j\binom kj$ は $d_k$ を割る。$k=2h,\ j=h$ から $h\binom{2h}h\mid d_{2h+1}$、$k=2h+1,\ j=h+1$ から $(2h+1)\binom{2h}h\mid d_{2h+1}$ である。$\gcd(h,2h+1)=1$ なので $h(2h+1)\binom{2h}h\mid d_{2h+1}$ で、$\binom{2h}h\ge4^h/(2h+1)$ より $d_{2h+1}\ge h4^h$ である。$m=2h+1\ge11$ なら $h\ge5$ で $h4^h=h2^{m-1}\ge2^m$ である。$m=2h+2\ge10$ なら $h\ge4$ で $d_m\ge h4^h=h2^{m-2}\ge2^m$ である。


したがって $\Pi< 2^{\log^5n}\le2^B\le d_B$ である。$d_B$ は $\Pi$ を割らないので、$\Pi$ を割らない $s\le B$ がある。$r_0=s/\gcd(s,n^{\lfloor\log B\rfloor})$ とおく。
$r_0$ は $n$ と互いに素である。実際、素数 $q$ が $s$ と $n$ の両方を割るとき、$q^{v_q(s)}\le s\le B$ より $v_q(s)\le\lfloor\log B\rfloor$ であり、$q$ は $n^{\lfloor\log B\rfloor}$ を少なくとも $v_q(s)$ 重に割るので、$r_0$ を割らない。また $r_0$ は $\prod_i(n^i-1)$ を割らない。割るなら $s$ が $\Pi$ を割ってしまうからである。よって $i\le L$ で $n^i\not\equiv1\pmod{r_0}$ で、$o_{r_0}(n)>L$、すなわち $o_{r_0}(n)>\log^2n$ である。段 2 の $r$ は最小なので、$r\le r_0\le B$ である。

合成数が通らないこと

算法が「素数」と出力したとする。段 4 で出力した場合は、段 3 を通っているので $a< n$ がみな $n$ と互いに素であり、$n$ は素数である。以下、段 6 で出力した場合に $n$ が素数であることを示す。
設定. 段 3・4 を通ったので $n>r$ で、$a\le r$ はすべて $n$ と互いに素である。$n=2,3$ では $r=3,5$ なので段 4 で止まり、$n=4$ は段 1 で止まるから、$n\ge5$ である。$n$ の素因数 $p$ を任意に 1 つとる。$p>r$ で、$\gcd(n,r)=1$ である。さらに $\varphi(r)\ge o_r(n)>\log^2n$ より $\sqrt{\varphi(r)}>\log n$ なので、
$$\ell\le\sqrt{\varphi(r)}\log n< \varphi(r)< r< p$$
である。$\mathbb F_p[X]$ の中で $f\equiv g$ と書いたら、環 $R:=\mathbb F_p[X]/(X^r-1)$ で等しいことをいう。$m\ge1$ が $f\in\mathbb F_p[X]$ について 内省的(introspective)であるとは、$f(X)^m\equiv f(X^m)$ が成り立つことをいう。

$n$、$p$、$n/p$ の内省性

$0\le a\le\ell$ について、$n$、$p$、$n/p$ はどれも $X+a$ について内省的である。

Frobenius 写像の単射性

$a=0$ は自明である。$a\ge1$ とする。$n$ は段 5 の合同式を $p$ で還元したものである。$p$ については、標数 $p$ なので $\mathbb F_p[X]$ の中で任意の $f$ について $f(X)^p=f(X^p)$ である。
$n/p$ を示す。$\sigma(f):=f(X^p)=f^p$ は環 $R$ の自己準同型である。$\gcd(p,r)=1$ なので $i\mapsto pi$ は $\mathbb Z/r\mathbb Z$ の全単射であり、$\sigma$ は基底 $1,X,\dots,X^{r-1}$ を置換するから、単射である。$g=(X+a)^{n/p}$、$h=X^{n/p}+a$ とおくと、$\sigma(g)=g^p=(X+a)^n\equiv X^n+a=\sigma(h)$ である。よって $g\equiv h$ である。

内省性の閉性

$m,m'$ が $f$ について内省的なら $mm'$ も $f$ について内省的である。$m$ が $f,g$ について内省的なら $fg$ についても内省的である。

後半は $(fg)^m=f^mg^m$ による。前半を示す。$f(X)^m-f(X^m)$ は $X^r-1$ で割り切れるので、$X$ に $X^{m'}$ を代入すると、$f(X^{m'})^m-f(X^{mm'})$ は $X^{m'r}-1$ で割り切れ、$X^{m'r}-1$ は $X^r-1$ で割り切れる。よって $f(X)^{mm'}\equiv f(X^{m'})^m\equiv f(X^{mm'})$ である。

$I=\{(n/p)^ip^j\mid i,j\ge0\}$、$P=\{\prod_{a=0}^\ell(X+a)^{e_a}\mid e_a\ge0\}$ とおく。2 つの補題から、$I$ のすべての元は $P$ のすべての元について内省的である。
2 つの有限集合を比べる。$G$ を $I$ の $(\mathbb Z/r\mathbb Z)^\times$ での像とし、$t=\lvert G\rvert$ とおく。$G$ は積で閉じているので部分群で、$n=(n/p)\cdot p\in I$ より $n$ を含むから、$t\ge o_r(n)>\log^2n$ であり、$t\le\varphi(r)$ である。$p\nmid r$ なので、$\mathbb F_p$ の代数閉包に 1 の原始 $r$ 乗根 $\zeta$ がある。$F=\mathbb F_p(\zeta)$ とする。$\zeta^r=1$ なので、$X\mapsto\zeta$ は環準同型 $R\to F$ を定める。$\mathcal G=\{f(\zeta)\mid f\in P\}\subset F$ とおく。内省性を $\zeta$ で評価すると、$f\in P$、$m\in I$ について
$$f(\zeta)^m=f(\zeta^m)$$
である。これが以下の 2 つの補題の鍵である。

$\mathcal G$ の下界

$\lvert\mathcal G\rvert\ge\binom{t+\ell}{t-1}$ である。

次数の低い多項式は値で区別される

$f\ne g$ を次数 $t-1$ 以下の $P$ の元とし、$f(\zeta)=g(\zeta)$ と仮定する。$m\in I$ について $f(\zeta^m)=f(\zeta)^m=g(\zeta)^m=g(\zeta^m)$ である。$\zeta$ の位数は $r$ なので、$\zeta^m$($m\bmod r\in G$)は相異なる $t$ 個の元であり、これらは次数 $t-1$ 以下の $0$ でない多項式 $f-g$ の根である。これは矛盾である。
よって $\lvert\mathcal G\rvert$ は、$P$ の中の次数 $t-1$ 以下の元の個数以上である。$\ell< p$ より $X,X+1,\dots,X+\ell$ は $\mathbb F_p[X]$ の相異なる既約元なので、指数 $(e_0,\dots,e_\ell)$($\sum e_a\le t-1$)ごとに異なる多項式が得られ、その個数は $\binom{t+\ell}{t-1}$ である。

$\mathcal G$ の上界

$n$ が $p$ の冪でなければ、$\lvert\mathcal G\rvert\le n^{\sqrt t}$ である。

鳩の巣原理

$k=\lfloor\sqrt t\rfloor$ とし、$\hat I=\{(n/p)^ip^j\mid0\le i,j\le k\}$ を考える。$n$ が $p$ の冪でなければ、$(n/p)^ip^j$ は $(i,j)$ ごとに異なる整数なので、$\lvert\hat I\rvert=(k+1)^2>t$ である。実際、$(n/p)^ip^j=(n/p)^{i'}p^{j'}$ で $i\ne i'$ なら、素因数分解から $n/p$ は $p$ の素因数しかもたず、$n$ が $p$ の冪になる。$i=i'$ なら $j=j'$ である。
鳩の巣原理により、$m_1>m_2$ が $\hat I$ にあって $m_1\equiv m_2\pmod r$ となる。$f\in P$ について $f(\zeta)^{m_1}=f(\zeta^{m_1})=f(\zeta^{m_2})=f(\zeta)^{m_2}$ なので、$\mathcal G$ の元はすべて $Y^{m_1}-Y^{m_2}$ の根である。根の個数は $m_1\le(n/p)^kp^k=n^k\le n^{\sqrt t}$ 以下である。

合成数が通らないこと

$s=\lfloor\sqrt t\log n\rfloor$ とおく。$t>\log^2n$ より $\sqrt t>\log n$ なので、$\sqrt t\log n< t$ であり $s\le t-1$ である。また $t\le\varphi(r)$ より $s\le\ell$ である。$n\ge5$ より $\sqrt t\log n>\log^2n>4$ なので $s\ge2$ である。$\binom{\ell+1+u}{u}$ は $\ell$ と $u$ のどちらについても単調増加なので、lem-aks-lower から
$$\lvert\mathcal G\rvert\ge\binom{\ell+1+(t-1)}{t-1}\ge\binom{\ell+1+s}{s}\ge\binom{2s+1}{s}\ge2^{s+1}>2^{\sqrt t\log n}=n^{\sqrt t}$$
である。ここで $\binom{2s+1}s\ge2^{s+1}$($s\ge2$)は、$s=2$ で $10\ge8$ であることと、$\binom{2s+3}{s+1}/\binom{2s+1}s=\frac{2(2s+3)}{s+2}\ge2$ による。lem-aks-upper と比べると、$n$ は $p$ の冪である。段 1 を通ったので $n=p$ であり、$n$ は素数である。

$\mathcal G$ の下界の形は Lenstra によるものである(AKS04 Lemma 4.7)。上の証明では 1 の原始 $r$ 乗根 $\zeta$ を直接使い、$p$ として $n$ の任意の素因数をとった。AKS04 は $o_r(p)>1$ となる素因数 $p$ と $X^r-1$ の既約因子で作った体を使う。Sho08 §21.2.2 でも $p$ の選び方は任意である。

計算量

多項式時間

def-aks-algorithm は、$O(\log^{16.5}n)$ のビット演算で実行できる。

段 5 が支配的である

lem-aks-r より $r=O(\log^5n)$ である。段 1 は $b\le\log n$ ごとに整数の $b$ 乗根を 2 分探索するので多項式時間で、段 2 は高々 $r$ 個の候補について $\log^2n$ 回程度の剰余の積を行い、段 3 は $r$ 回の最大公約数の計算である。これらは段 5 より小さい。
段 5 は $\ell\le\sqrt r\log n$ 回の冪計算である。1 回の冪は繰り返し 2 乗で $O(\log n)$ 回の積で、$X^r-1$ を法とした積は係数の積と和が $O(r^2)$ 回で、係数の演算は $O(\log^2n)$ のビット演算である。合計は $\sqrt r\log n\cdot\log n\cdot r^2\cdot\log^2n=r^{5/2}\log^4n=O(\log^{16.5}n)$ である。

同じ見積りが Sho08 Theorem 21.3(p. 551)にある。

速い乗算と改良

以下はこの記事では証明しない。多項式と整数の高速な乗算を使うと、段 5 は $\tilde O(r^{3/2}\log^3n)$ となり、全体は $\tilde O(\log^{21/2}n)$ である($\tilde O$ は対数の多項式倍を無視する。AKS04 Theorem 5.1)。$r$ の評価を改良して指数を下げることができる(同 Theorem 5.3 は $\tilde O(\log^{15/2}n)$)。AKS04 §5 は、Lenstra と Pomerance が算法を変更して $\tilde O(\log^6n)$ を証明したと述べる。

例

小さい $n$ の $r$ と $\ell$

次の値は計算機で求めた。

$n$$\log^2n$$r$$\varphi(r)$$\ell$止まる段
$31$$24.5$$29$$28$$26$段 6(素数)
$97$$43.6$$59$$58$$50$段 6(素数)
$561=3\cdot11\cdot17$$83.4$$89$$88$$85$段 3($a=3$)
$1009$$99.6$$107$$106$$102$段 6(素数)
$74513=269\cdot277$$262.0$$263$$262$$261$段 5($a=1$)
$2^{61}-1$$3721$$3733$$3732$$3726$段 6(素数)

$n=2,\dots,3000$ を全部走らせると、結果はすべて篩と一致した。この範囲では、段 4 で止まる素数は $41$ 以下の 11 個で、残りの素数 419 個は段 6 まで進み、合成数は段 1 か段 3 ですべて止まる。$r>\log^2n$ なので、段 5 に届く合成数は最小の素因数が $\log^2n$ を超えるものだけである。そのような完全冪でない合成数の最小の例が $74513$ であることも同じ方法で確かめた。AKS04 §4 の段 4 の脚注は、Lemma 4.3 の $r\le\log^5n$ から段 4 が意味をもつのは $n\le5690034$ の場合だけであると述べている。

Sho08 の第 21 章の冒頭は、この算法は理論上は重要でも実用上の意味はほとんどなく、Miller-Rabin素数判定法 のような確率的な判定法のほうがはるかに効率的であると述べている。

反例:仮定を外すと成り立たないこと

変更反例成り立たなくなること
段 2 の $o_r(n)>\log^2n$ を外す$n=1729=7\cdot13\cdot19$、$r=3$(ex-aks-carmichael)thm-aks-main の結論:すべての $a$ で合同式が成り立つが $n$ は合成数
lem-aks-r の $\max$ の $3$ を外す$n=2$不等式 $r\le\lceil\log^5n\rceil=1$:実際は $r=3$
$d_m\ge2^m$ の $m\ge10$ を外す$m=6$下界そのもの:$d_6=60< 64$(実際に成り立たないのは $m=1,2,3,4,6$ だけ。$m=7,8,9$ でも成り立つ)
$\binom{2s+1}s\ge2^{s+1}$ の $s\ge2$ を外す$s=1$不等式そのもの:$\binom31=3< 4$
$r$ が小さすぎるとき

$n=1729$、$r=3$ とする。素因数 $p=7,13,19$ はどれも $r$ より大きく、$n$ は平方自由で完全冪でなく、$p-1$ は $n-1=1728$ を割り、$3$ は $p-1$ を割る。$\gcd(n,3)=1$ だが $o_3(1729)=1$ である。
すべての $a$ で $(X+a)^n\equiv X^n+a\pmod{X^3-1,n}$ である。実際、$n\equiv1\pmod3$ なので $X^n\equiv X$ である。中国剰余定理 により $p$ ごとに確かめればよい。$3\mid p-1$ なので $\mathbb F_p[X]/(X^3-1)\cong\mathbb F_p^3$($X$ は 1 の 3 乗根 $\omega$ に写る)で、各成分で $(\omega+a)^n=\omega+a$ である。これは $p-1\mid n-1$ と Fermatの小定理 による。計算機でも $a=1,\dots,1729$ を全部確かめた。
$r=1$ の場合は $(1+a)^n\equiv1+a\pmod n$ で、Fermat の判定そのものである。$1729$ は Carmichael数 であり、この例の合同式は Fermat の判定と同じようにすり抜けられている。lem-aks-lower と lem-aks-upper の比較には $t>\log^2n$ が要り、段 2 の条件がそれを保証する。

段 1 を外すと、証明からは「$n$ は $p$ の冪」までしか出ない。段 1 は証明のこの段階で使う。素数の冪を実際に段 5 が通すかどうかについて、この記事は何も主張しない。段 3 のほうは、完全冪でない $n\le2000$ で $n>r$ のとき、段 3 を飛ばしても段 5 を通る合成数はなかった。

補足

1 つの $a$ で足りるか

AKS04 §6 は次の予想を挙げ、$r\le100$、$n\le10^{10}$ で確かめられていると述べている:素数 $r$ が $n$ を割らず $(X-1)^n\equiv X^n-1\pmod{X^r-1,n}$ なら、$n$ は素数であるか $n^2\equiv1\pmod r$ である。同所は、Lenstra と Pomerance の発見的な議論がこの予想は偽であることを示唆するとも述べる。
除外条件 $n^2\equiv1\pmod r$ は外せない。ex-aks-carmichael の $n=1729$、$r=3$ は $(X-1)^n\equiv X^n-1$ をみたす合成数で、$1729^2\equiv1\pmod3$ である。また $a$ を変えると結果が変わることがある。$n=341=11\cdot31$、$r=3$ では $a=1$ で合同式が成り立ち、$a=2$ と $a=-1$ では成り立たない(計算機で確かめた)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する