素数判定法

同義語：素数判定primality testprimality testing

概要

前提知識: 素数, Fermatの小定理, 原始根, 計算整数論

素数判定法（primality test）は、与えられた整数 $n\ge2$ が素数かどうかを判定する手順である。素因数分解を求めなくても、素数かどうかだけなら速く判定できる。この違いが現代の計算整数論と暗号の土台になっている。判定法は大きく 2 種類に分かれる。Fermat の小定理とその精密化が素数で成り立つことを使い、それを破る底を合成数の証拠として探す確率的な判定法（Miller-Rabin素数判定法など）と、乗法群の元の位数から素数であることを証明する判定法（thm-prt-lucas、thm-prt-pocklington）である。後者は $n-1$ の素因数分解の一部を要求するが、$n$ が素数であることの証明書を与える。さらに、どんな $n$ に対しても決定的に多項式時間で判定する方法が存在する（prop-prt-aks-identity とその後の注意）。
個々の判定法の詳しい解析は、計算整数論・擬素数・Carmichael数・Jacobi記号・Miller-Rabin素数判定法・Mersenne素数・Fermat数の各記事にある。この記事は判定法を見渡し、素数であることを証明する側の判定法を扱う。

定義

素数判定法

整数 $n\ge2$ を入力として「素数」か「合成数」を出力する手順を素数判定法という。

出力がつねに正しいものを決定的（deterministic）な判定法という。
途中で乱数を使い、$n$ が素数なら必ず「素数（おそらく素数）」と出力し、$n$ が合成数なら誤って「おそらく素数」と出力する確率が決まった値以下であるものを確率的（probabilistic）な判定法という。
手間は $n$ のビット長 $\operatorname{len}(n)$（計算整数論の記事の定義「ビット長」）で測り、ビット長の多項式で抑えられる手間の判定法を多項式時間の判定法という。

$n$ が合成数であることを示すデータで、それが正しいことを速く確かめられるものを合成数の証拠（witness）という。$1< d< n$ となる約数 $d$ や、$a^{n-1}\not\equiv1\pmod n$ となる整数 $a$（$1\le a\le n-1$）がその例である。逆に、$n$ が素数であることを示すデータで速く確かめられるものを素数の証明書（primality certificate）という。

直感

合成数であることは、証拠が 1 つ見つかれば終わる。素数であることは「どこを探しても証拠がない」ことなので、そのままでは示しにくい。素数を証明する判定法は、乗法群 $(\mathbb{Z}/n\mathbb{Z})^\times$ の大きさを使う。この群の位数 $\varphi(n)$ は、$n$ が素数のときに限って $n-1$ に等しい。そこで「位数 $n-1$ の元がある」ことを示せば、群が大きすぎて $n$ は素数しかありえない。位数がちょうど $n-1$ であることを確かめるには、$n-1$ の素因数を知る必要がある。

試し割りと Wilson の定理

試し割り

$n\ge2$ が合成数なら、$n$ は $\sqrt n$ 以下の素因数をもつ。したがって $n$ が $\sqrt n$ 以下のどの素数でも割り切れなければ、$n$ は素数である。

$n=ab$、$1< a\le b< n$ と書けば $a^2\le ab=n$ なので $a\le\sqrt n$ であり、$a$ の素因数は $\sqrt n$ 以下で $n$ を割る。$\square$

試し割りは素因数も見つけるが、割り算の回数は $\sqrt n\approx2^{\operatorname{len}(n)/2}$ の程度で、ビット長について指数関数的である（Sho08 §10.1, p. 306）。Wilsonの定理の $(n-1)!\equiv-1\pmod n$ も素数であることの必要十分条件だが、$(n-1)!$ を $n$ で割った余りを素直に計算すると $n$ 回程度の掛け算になり、やはりビット長について指数関数的である。

確率的な判定法

Fermatの小定理により、$n$ が素数なら $n$ と互いに素なすべての $a$ で $a^{n-1}\equiv1\pmod n$ である。この条件を破る $a$ は合成数の証拠になり、計算整数論の記事の定理「反復二乗法の正しさと手間」により $\operatorname{len}(n)$ の多項式の手間で確かめられる。底 $a$ をでたらめに選んで試すと、次のように合成数を見逃す割合が抑えられる。

判定法	判定に使う条件	合成数 $n$ でこの条件を満たす底の個数	記事の定理
Fermat の判定	$a^{n-1}\equiv1$	Carmichael 数でなければ $(n-1)/2$ 以下	計算整数論「Fermat の判定を通る底の個数」
Euler–Jacobi の判定（奇数 $n$）	$a^{(n-1)/2}\equiv\left(\frac an\right)$	$\varphi(n)/2$ 以下	Jacobi記号「Euler–Jacobi の判定の誤り率」
Miller–Rabin の判定（奇数 $n\ge3$）	$a^t\equiv1$ または $a^{2^jt}\equiv-1$（$n-1=2^st$）	$(n-1)/4$ 以下	Miller-Rabin素数判定法「判定を通過する底の個数」

Fermat の判定には、$n$ と互いに素なすべての底で条件を満たす合成数（Carmichael数）があり、それが無限に存在する（Carmichael数の記事の定理「Carmichael数の無限性（Alford–Granville–Pomerance）」）ので弱点が残る。Euler–Jacobi の判定と Miller–Rabin の判定にはこの例外がない。Miller–Rabin の判定を独立に $k$ 回くり返すと、合成数を「おそらく素数」と誤る確率は $4^{-k}$ 以下になる（Miller-Rabin素数判定法の記事の系「合成数を見逃す確率」）。これらは多項式時間の確率的判定法であり、後で述べる決定的な判定法よりはるかに速い（Sho08 Chapter 21 の冒頭, p. 548）。ただし出力「おそらく素数」は合成数の証拠が見つからなかったことを意味するだけで、素数の証明書にはならない。

素数であることの証明

Lucas の判定法

整数 $n\ge2$ について、次の 2 条件は同値である。

$n$ は素数である。
整数 $a$ で、$a^{n-1}\equiv1\pmod n$ であり、かつ $n-1$ を割るすべての素数 $q$ について $a^{(n-1)/q}\not\equiv1\pmod n$ となるものがある。

2 ⇒ 1．$a^{n-1}\equiv1$ から $a$ は $n$ と互いに素である。$d:=\operatorname{ord}_n(a)$ とおくと $d\mid n-1$ である（原始根の記事の命題「位数の整除性」）。$d< n-1$ なら $(n-1)/d>1$ の素因数 $q$ がとれ、$q\mid n-1$ かつ $d\mid(n-1)/q$ なので $a^{(n-1)/q}\equiv1$ となって仮定に反する。よって $d=n-1$ である。一方、同記事の命題「位数の整除性」の 2 により $d\mid\varphi(n)$ なので、$n-1\le\varphi(n)$ である。$n$ が合成数なら、$1< m< n$ となる約数 $m$ は $n$ と互いに素でないので $\varphi(n)\le n-2$ となり矛盾する。よって $n$ は素数である。
1 ⇒ 2．$n$ が素数なら原始根 $g$ がある（原始根の記事の定理「素数を法とする原始根の存在」）。$\varphi(n)=n-1$ なので、同記事の命題「原始根の判定法」により $a:=g$ が 2 の条件を満たす。$\square$

$n-1$ の素因数分解がわかっていれば、2 の条件は $\operatorname{len}(n)$ の多項式の手間で確かめられる。条件を満たす $a$（素数 $n$ の原始根）は、素数 $n$ では $\varphi(n-1)$ 個あるので（原始根の記事の系「原始根の個数」）、でたらめに選んでも見つかりやすい。難しいのは $n-1$ の素因数分解のほうである。
$n-1$ の素因数 $q$ が素数であることも同じ方法で証明できる。$n$ に対して $a$、$n-1$ の素因数分解、各素因数の同じ形のデータ、と再帰的に並べたものは素数の証明書になる。素数の大きさについての帰納法により、どの素数にもこの形の証明書があり、各段の確認は冪乗剰余と掛け算だけで済む。

Pocklington の判定法

$n-1$ を完全に分解しなくても、$\sqrt n$ より大きい部分さえ分解できれば足りる。

Pocklington の判定法

$n\ge2$ を整数とし、$n-1=FR$（$F,R$ は正の整数）で $F>\sqrt n$ とする。$F$ を割る各素数 $q$ について、整数 $a_q$ で
$$ a_q^{\,n-1}\equiv1\pmod n,\qquad \gcd\bigl(a_q^{(n-1)/q}-1,\ n\bigr)=1 $$
となるものがあれば、$n$ は素数である。

$p$ を $n$ の素因数とし、$F$ が $p-1$ を割ることを示す。$q$ を $F$ の素因数、$q^e$ を $F$ を割る $q$ の最大の冪とし、$b:=a_q^{(n-1)/q^e}$ とおく（$q^e\mid n-1$ なので整数の冪である）。$p\mid n$ なので $b^{q^e}=a_q^{n-1}\equiv1\pmod p$ で、とくに $p\nmid b$ である。また $b^{q^{e-1}}=a_q^{(n-1)/q}$ について、$\gcd(a_q^{(n-1)/q}-1,n)=1$ から $p\nmid a_q^{(n-1)/q}-1$、すなわち $b^{q^{e-1}}\not\equiv1\pmod p$ である。よって $b$ の $p$ を法とする位数は $q^e$ を割り $q^{e-1}$ を割らないので、ちょうど $q^e$ である。Fermatの小定理により位数は $p-1$ を割るので $q^e\mid p-1$ である。$F$ のすべての素因数について合わせて $F\mid p-1$、とくに $p\ge F+1>\sqrt n$ である。$n$ のすべての素因数が $\sqrt n$ より大きいので、prop-prt-trial-division により $n$ は素数である。$\square$

$F=n-1$ とし、すべての $q$ で同じ $a$ を使えば、Lucas の判定法の 2 ⇒ 1 とほぼ同じ主張になる（$\gcd$ の条件は $\not\equiv1$ より強い）。Pocklington の判定法の利点は、底 $a_q$ を素因数ごとに替えてよいことと、$n-1$ の分解が $\sqrt n$ を超えたところで止めてよいことである。

Proth の判定法

$m\ge1$、$k$ を $1\le k<2^m$ の奇数とし、$n:=k\cdot2^m+1$ とおく。ある整数 $a$ について $a^{(n-1)/2}\equiv-1\pmod n$ なら、$n$ は素数である。

$F:=2^m$、$R:=k$ とする。$k\le2^m-1$ から $n\le2^{2m}-2^m+1<2^{2m}=F^2$ で、$F>\sqrt n$ である。$F$ の素因数は $q=2$ だけで、$a^{n-1}=\bigl(a^{(n-1)/2}\bigr)^2\equiv1\pmod n$、$a^{(n-1)/2}-1\equiv-2\pmod n$ である。$n$ は奇数なので $\gcd(a^{(n-1)/2}-1,n)=\gcd(-2,n)=1$ となり、thm-prt-pocklington から $n$ は素数である。$\square$

Fermat 数 $F_m=2^{2^m}+1$ は、cor-prt-proth で $k=1$、$2$ の指数を $2^m$ とした場合である。$a=3$ についての Proth の判定法の条件は Fermat数の記事の命題「Pépinの判定法」の条件そのものである。Pépin の判定法は、逆に $F_m$ が素数ならこの条件が成り立つことも平方剰余の相互法則から示している。$n-1$ ではなく $n+1$ の分解を使う判定法もあり、Mersenne 数 $2^p-1$ に対する Mersenne素数の記事の定理「Lucas–Lehmerの判定法」がその代表である。

多項式時間の決定的な判定

多項式の合同式による特徴づけ

$n\ge2$ とし、$a$ を $n$ と互いに素な整数とする。$n$ が素数であることと、多項式環 $(\mathbb{Z}/n\mathbb{Z})[X]$ の中で
$$ (X+a)^n=X^n+a $$
が成り立つことは同値である。

$(X+a)^n=\sum_{i=0}^n\binom niX^{n-i}a^i$ である。$n$ が素数なら、$0< i< n$ について $\binom ni=\frac{n!}{i!\,(n-i)!}$ の分子は $n$ で割り切れ、分母は割り切れないので $n\mid\binom ni$ であり、Fermatの小定理から $a^n\equiv a$ なので等式が成り立つ。$n$ が合成数なら、素因数 $p$ と $p^k\,\|\,n$（$p^k\mid n$、$p^{k+1}\nmid n$）をとる。$\binom np=\frac{n(n-1)\cdots(n-p+1)}{p!}$ の分子のうち $p$ で割り切れるのは $n$ だけ（$n-p< n-i< n$ には $p$ の倍数がない）なので、分子はちょうど $p^k$ で、$p!$ はちょうど $p$ で割り切れる。よって $p^k\nmid\binom np$ である。$p\nmid a$ なので $X^{n-p}$ の係数 $\binom npa^p$ は $n$ で割り切れず、$0< p< n$ だから右辺の同じ係数 $0$ と一致しない。$\square$

この特徴づけ自体は、左辺を展開するのに $n$ 程度の手間がかかるので速い判定法ではない（Sho08 Theorem 21.1, pp. 548–549）。Agrawal・Kayal・Saxena は、適当に選んだ小さい $r$ について $X^r-1$ を法とした合同式を $\operatorname{len}(n)$ の多項式個の $a$ で確かめれば素数かどうかが決まることを示し、決定的な多項式時間の素数判定法（AKS 法）を与えた。手間は $O(\operatorname{len}(n)^{16.5})$ で抑えられる（Sho08 §21.2, Theorem 21.3–21.5, pp. 549–558。この記事では証明しない）。

例

Lucas の判定法

$n=97$、$n-1=96=2^5\cdot3$ とする。$a=5$ では $5^{96}\equiv1$、$5^{48}\equiv-1$、$5^{32}\equiv35\pmod{97}$ で、$q=2,3$ のどちらでも $a^{(n-1)/q}\not\equiv1$ である。thm-prt-lucas により $97$ は素数であり、$5$ は $97$ の原始根である。

Pocklington の判定法

$n=10007$ では $n-1=2\cdot5003$ で、$5003$ は $70$ 以下の素数で割り切れないので素数である（prop-prt-trial-division、$70^2<5003<71^2$）。$F=5003>\sqrt{10007}\approx100.03$ とする。$a=2$ について $2^{10006}\equiv1\pmod{10007}$、$2^{10006/5003}=4$ で $\gcd(3,10007)=1$ である。thm-prt-pocklington により $10007$ は素数である。$n-1$ の残りの因数 $2$ について何も確かめなくてよい点が thm-prt-lucas との違いである。

Proth の判定法

$n=769=3\cdot2^8+1$ では $k=3<2^8$ である。$a=7$ について $7^{384}\equiv-1\pmod{769}$ なので、cor-prt-proth により $769$ は素数である。

反例

各行は、記事の主張の仮定を 1 つだけ外したときに結論が崩れる例である。

外す条件	反例	成り立たなくなること
すべての $q$ で $a^{(n-1)/q}\not\equiv1$（thm-prt-lucas）	$n=15$、$a=4$	$n$ が素数であること
$a^{n-1}\equiv1$（thm-prt-lucas）	$n=9$、$a=2$	$n$ が素数であること
$F>\sqrt n$（thm-prt-pocklington）	$n=15$、$F=2$、$a_2=14$	$n$ が素数であること
$k<2^m$（cor-prt-proth）	$n=15=7\cdot2+1$、$a=14$	$n$ が素数であること
$a$ と $n$ が互いに素（prop-prt-aks-identity）	$n=4$、$a=0$	等式から $n$ が素数であること

反例の確認

各行で、外した条件以外は満たされている。

各行の確認を開く

1 行目：$n-1=14=2\cdot7$。$4^2=16\equiv1\pmod{15}$ から $4^{14}\equiv1$ で、$q=2$ については $4^7\equiv4\not\equiv1$ だが、$q=7$ については $4^2\equiv1$ である。2 行目：$n-1=8$ の素因数は $2$ だけで、$2^4=16\equiv7\not\equiv1\pmod9$ だが、$2^8=256\equiv4\not\equiv1\pmod 9$ である。3 行目：$14\equiv-1\pmod{15}$ なので $14^{14}\equiv1$、$14^7\equiv-1$ で $\gcd(14^7-1,15)=\gcd(-2,15)=1$ だが、$F=2<\sqrt{15}$ である。4 行目：$k=7$ は奇数で $14^7\equiv-1\pmod{15}$ だが、$k=7\ge2^1$ である。5 行目：$(X+0)^4=X^4+0$ は成り立つが、$\gcd(0,4)=4$ である。いずれの $n$ も合成数である。

補足

Lucas・Pocklington・Proth・Pépin・Lucas–Lehmer の判定法は、どれも「ある有限群の元の位数が大きいことから、$n$ の素因数が大きいことを導く」という同じ考え方に立っている。$n-1$ の分解を使うときは群 $(\mathbb{Z}/p\mathbb{Z})^\times$ が、Lucas–Lehmer の判定法では $\mathbb{Z}[\sqrt3]$ の $2+\sqrt3$ を $n$ の素因数を法として見たものの位数が、その役を果たす。素数判定は素因数分解よりずっと易しく、素数判定が多項式時間でできる一方で、素因数分解の多項式時間の方法は知られていない（計算整数論の記事の注意「多項式時間で解ける問題と、難しいと考えられている問題」）。この差が RSA暗号を支えている。