合同式に基づく古典的な素数判定法

提供: Mathpedia


$\newcommand{\NN}{\mathbb{N}}$ $\newcommand{\ZZ}{\mathbb{Z}}$ $\newcommand{\QQ}{\mathbb{Q}}$ $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\CC}{\mathbb{C}}$ $\newcommand{\LCM}{\mathrm{LCM}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$

この記事では、合同式を用いた古典的な素数判定法について解説する。

Wilsonの定理

自然数 $N$ が素数 $\Longleftrightarrow$ $(N-1)!\equiv -1\mathmod{N}$

Proof.

$N=2$ のときは $(N-1)!=1$ なので、$(N-1)!\equiv -1\mathmod{N}$ は明らか。

$N$ を奇素数とし、$N$ を法とする原始根をひとつとり、それを $g$ とすると、 $g, g^2, \ldots, g^{N-1}=1\mathmod{N}$ は $N$ を法とする既約剰余類全体と一致する。 よって $$(N-1)!\equiv \prod_{k=1}^{N-1} g^k\equiv g^{(N-1)N/2}\mathmod{N}$$ となる。$N$ は奇数なので $$(N-1)!\equiv g^{(N-1)/2}\equiv -1\mathmod{N}$$ が成り立つ。

$N=4$ は合成数で $(N-1)!=6\equiv 2\mathmod{N}$ だから、$(N-1)!\not\equiv -1\mathmod{N}$.

$N$ が $4$ より大きい合成数のとき、$N=ab, 2\leq a, b\leq N-1$ となる $a, b$ をとる。 $a\neq b$ のとき $a, b$ はともに $1, 2, \ldots, N-1$ のなかにあらわれるから $$N=ab\mid (N-1)!$$ となる。$a=b$ のときは $N>4$ より $a=\sqrt{N}<N/2$ となるので、 $a, 2a$ がともに $1, 2, \ldots, N-1$ のなかにあらわれるから $$N=a^2\mid a\times 2a\mid (N-1)!$$ となる。よって $N$ が $4$ より大きい合成数のとき $(N-1)!\equiv 0\mathmod{N}$ となる。

□

$N$ が素数のとき $(N-1)!\equiv -1\mathmod{N}$ となることについては、原始根を用いない証明もある。

Proof.

$N$ が素数のときFermatの小定理より、 $$X^{N-1}-1\equiv 0\mathmod{N}$$ はすべての既約剰余類 $1, 2, \ldots, N-1\mathmod{N}$ を解にもつ。よって合同式:定理5.3より $$X^{N-1}-1\equiv (X-1)(X-2)\cdots (X-(N-1))Q(X)\mathmod{N}$$ となる多項式 $Q(X)$ が存在するが、左辺は $N-1$ 次式で、最高次の係数は1だから $$Q(X)\equiv 1\mathmod{N}$$ つまり $$X^{N-1}-1\equiv (X-1)(X-2)\cdots (X-(N-1))\mathmod{N}$$ となる。$X=0$ を代入すると $$-1\equiv (-1)^{N-1} (N-1)!\mathmod{N}$$ となる。$N=2$ のとき $-1\equiv 1\mathmod{2}$ となり、$N$ が奇素数のとき $(-1)^{N-1}=1$ となるから、 いずれにせよ $$-1\equiv (N-1)!\mathmod{N}$$ が成り立つ。

□

Wilsonの定理は、与えられた自然数 $N$ が素数であることの必要十分条件を非常に単純な形で与えている。 しかし、階乗を速く計算するアルゴリズムが知られていないため、この定理を素数判定に用いるのは実用的ではない。

一方で、素数の集合を多項式で特徴づける問題を考える上では重要な役割を果たす。というのは上記の条件は階乗を含む方程式 $$(N-1)!-aN=-1$$ の整数解 $a$ が存在することと一致するが、この方程式は指数関数を含むが階乗を含まない不定方程式に還元され、最終的に 多項式の不定方程式に還元されることが知られているからである。言い換えれば、$N$ が素数であることの必要十分条件は $N$ をパラメータにもつ、ある不定方程式が整数解をもつことである。

この話題は不定方程式の整数解の有無を判定する一般的なアルゴリズムが存在するか否かを問うHilbertの第10問題の（否定的）解決とも深く関わっている。 Davis, 1973を参照。

Fermatの小定理の逆

Wilsonの定理は与えられた数が素数かどうかを判定するには実用的ではない。一方で、べき乗 $a^n$ は速く計算することができるので、 Fermatの小定理における合同式 $$a^{N-1}\equiv 1\mathmod{N} \quad \quad (1)$$ は成立するかどうかの判定は比較的短い時間で可能である。

しかし、Fermatの小定理の逆は一般には成り立たない。 $a\equiv \pm 1\mathmod{N}$ のような自明な反例は除いても、たとえば $a=2$ の場合でさえ $$2^{N-1}\equiv 1\mathmod{N}$$ が成立する合成数 $N$ は存在する。$N=341, 561, 645, 1105, \ldots$ である (OEIS: A001567)。 合同式 $(1)$ が成立する合成数 $N$ を $a$ を底とするFermat擬素数という。さらに、$N=561, 1105, 1729, \ldots$ (OEIS: A002997) のように $N$ と互いに素な任意の $a$ について $(1)$ が成立する合成数が無限に多く存在することが知られている。このような合成数をCarmichael数という。

Carmichael数に対しては $(1)$ が成立しない $a$ は $N$ と互いに素でない整数のみである。そのような $a$ は $N$ の倍数であるか、 $N$ との間に $1$ か $N$ 以外の公約数をもつものに限られる。前者のようなものは見つけても意味がなく、後者のようなものを見つければ $N$ との最大公約数をとることで $N$ の自明でない（$1$ と自分自身以外の）約数を見つけることができる。つまり、Carmichael数に対しては $(1)$ が成立しない $a$ を見つけるのは $N$ の自明でない約数を見つけるのと同程度に困難な作業である。

Eulerの定理に記したように、$N$ が素数であることは $\varphi(N)=N-1$ であることと同値である。 このこと自体を素数判定に直接用いるのはやはり実用的ではない。$\varphi(N)$ を速く計算するアルゴリズムは知られていないからである。

しかし、このことから、位数が $N-1$ に等しい整数 $a$ が存在すれば、Eulerの定理より $\varphi(N)$ は $N-1$ で割り切れるので、 $\varphi(N)=N-1$ でなければならず、$N$ が素数であることがわかる。それで $(1)$ が成り立つが、$1\leq d\leq N-2$ に対して $$a^d\not\equiv 1\mathmod{N}$$ となる整数 $a$ が存在するとき、$N$ を法とする $a$ の位数は $N-1$ に等しいから、$N$ は素数である（Lucas, 1878, p. 302）。 すなわち、$(1)$ が成立し、かつ一定の条件が成り立てば $N$ が素数であることが示せるのである。

Lucasはさらに、$(1)$ が成り立つが、$N-1$ 自身を除く $N-1$ の約数 $d$ に対して、 $$a^d\not\equiv 1\mathmod{N}$$ が成り立つような整数 $a$ が存在するとき、$N$ を法とする $a$ の位数は $N-1$ に等しいから、$N$ は素数であることを示した（Lucas, 1891, p. 441）。 Lehmerはこれを改良し、BrillhartとSelfridgeはさらに改良した。

定理2.1

(Lehmer, 1927, Theorem 2) $N$ が素数であるための必要十分条件は $$a^{N-1}\equiv 1\mathmod{N}$$ となるが、$N-1$ のすべての素因数 $q$ に対して $$a^{(N-1)/q}\not\equiv 1\mathmod{N} \quad \quad (2)$$ となる整数 $a$ が存在することである。

Proof.

$N$ が素数ならば、$N$ の原始根 $a$ について $(1), (2)$ はともに成り立つ。逆に $(1), (2)$ がともに成り立つとき $N$ が素数であることを示す。

$(1)$ が成り立つとき、$N$ を法とする $a$ の位数は $N-1$ の約数となる。 そこで $N$ を法とする $a$ の位数を $(N-1)/d$ とおく。 $q\mid d$ のとき $N$ を法とする $a$ の位数は $(N-1)/q$ の約数となるから $$a^{(N-1)/q}\equiv 1\mathmod{N}$$ となって、$(2)$ が成り立たなくなる。よって $d$ は $N-1$ の素因数 $q$ では割り切れないから $d=1$ つまり $N$ を法とする $a$ の位数は $N-1$ である。 Eulerの定理より $N-1$ は $\varphi(N)$ を割り切るので、$\varphi(N)=N-1$ となる。 よって $N$ は素数である。

□

定理2.2

(Brillhart and Selfridge, 1967, Theorem 2) $N$ が素数であるための必要十分条件は $N-1$ のすべての素因数 $q$ に対して $$a^{N-1}\equiv 1\mathmod{N}$$ となるが $$a^{(N-1)/q}\not\equiv 1\mathmod{N}$$ となる整数 $a=a(q)$ が存在することである（$a(q)$ は $q$ によって異なっていてもよい）。

Proof.

$N$ が素数ならば、$N$ の原始根 $a$ について $(1), (2)$ はともに成り立つ。

$$N-1=\prod_{i=1}^r q_i^{e_i}$$ と素因数分解し、$a_i=a(q_i)$ とおく。

各 $j=1, 2, \ldots, r$ について $$a_j^{N-1}\equiv 1\mathmod{N}$$ となるが $$a_j^{(N-1)/q_j}\not\equiv 1\mathmod{N}$$ が成り立つ。$N$ を法とする $a_j$ の位数を $d_j$ とおくと位数の定義で述べたように $d_j$ は $N-1$ を割り切るが $(N-1)/q_j$ を割り切らない。 $$d_j=\prod_{i=1}^r q_i^{f_i}$$ とおくと $d_j\mid (N-1)$ より $0\leq f_i\leq e_i$ が成り立つ。$f_j\leq e_j-1$ とすると $d_j$ は $(N-1)/q_j$ を割り切ってしまうので、$f_j=e_j$ となる。つまり $q_j^{e_j}$ は $d_j$ を割り切る。 定理4.1より $d_j$ は $\varphi(N)$ を割り切るから $q_j^{e_j}$ は $\varphi(N)$ を割り切る。

これが各 $j=1, 2, \ldots, r$ について成り立つので結局 $N-1$ が $\varphi(N)$ を割り切ることになり、 $\varphi(N)=N-1$ であるから、 $N$ は素数である。

□


Prothの判定法

Prothは $h\times 2^n+1$ の形の数に対する素数判定法を発見した。

定理3.1

(Proth, 1878) $$N=h\times 2^n+1, h<2^n$$ となる正の整数 $h, n>0$ が存在するとする。このとき $N$ が素数であるための必要十分条件は $$a^{(N-1)/2}\equiv -1\mathmod{N}\quad \quad (3)$$ となる整数 $a$ が存在することである。

Proof.

$N$ が素数ならば、$N$ の原始根 $a$ について $(3)$ が成り立つ。

$(3)$ が成り立つ $a$ をとり、$N$ の素因数 $p$ をひとつとると $$a^{(N-1)/2}\equiv -1\mathmod{p}\quad \quad (4)$$ も成り立つ。さらに、この両辺を$2$乗すると $$a^{N-1}\equiv 1\mathmod{p}$$ も成り立つから、$p$ を法とする $a$ の位数を $d$ とおくと $d$ は $N-1=h\times 2^n$ の約数である。 $(4)$ より $d$ は $(N-1)/2=h\times 2^{n-1}$ の約数ではない。よって $d$ は $2^n$ の倍数であるから 合同式:定理4.1より $$2^n\mid d\mid\varphi(p)=p-1$$ となり $$p\equiv 1\mathmod{2^n}$$ が成り立つ。とくに $p\geq 2^n+1$ が成り立つ。 $N$ が合成数ならば、$p_1 p_2\mid N$ となる素数 $p_1, p_2$ （$p_1=p_2$ であってもよい） が存在するので $$N\geq p_1 p_2\geq (2^n+1)^2 > 2^{2n}+1>h\times 2^n+1$$ となって、矛盾するから $N$ は素数である。

□

たとえば $$2^{2^{73}}\equiv -1\mathmod{5\times 2^{75}+1}$$ であるが、$5\times 2^{75}+1=10\times 2^{74}+1$ かつ $10<2^{74}$ であるから $5\times 2^{75}+1$ は素数である。なお、このことはFermat数 $$F_{73}=2^{2^{73}}+1$$ が $5\times 2^{75}+1$ を素因数にもつことも示している (Morehead, 1906)。

Prothの判定法は、Pocklingtonによる次の結果に一般化される。

定理3.2

(Pocklington, 1914) $$N=FR+1, \gcd(F, R)=1$$ かつ、$F$ の各素因数 $q$ に対して $$a^{N-1}\equiv 1\mathmod{N}$$ かつ $$\gcd(a^{(N-1)/q}-1, N)=1 \quad \quad (5)$$ となる $a=a(q)$ が存在するとき、$N$ の素因数は $F$ を法として $1$ と合同である。 とくに $F+1>\sqrt{N}$ ならば $N$ は素数である。

Proof.

$$F=\prod_{i=1}^r q_i^{e_i}$$ と素因数分解し、$a_i=a(q_i)$ とおく。 $p$ を $N$ の素因数とし、$p$ を法とする $a_i$ の位数を $d_i$ とおく。

各 $j$ について、$(5)$ より $p$ は $a_j^{(N-1)/q_j}-1$ を割り切らない、つまり $$a_j^{(N-1)/q_j}\not\equiv 1\mathmod{p}$$ となるから、定理2.2の証明と同様にして $$q_j^{e_j}\mid d_j\mid \varphi(p)=p-1$$ が成り立つ。

よって $p-1$ は $\prod_i q_i^{e_i}=F$ で割り切れる。

□


参考文献

この記事の執筆にあたっては P. Ribenboim, The New Book of Prime Number Records', 3rd edition, Springer, 1996 のChapter 2 および Chapter 4, とくに Section 2. III, p.p. 48--53 を参考とした。

「https://math.jp/w/index.php?title=合同式に基づく古典的な素数判定法&oldid=12239」から取得