初等整数論/合同式に基づく素数判定

合同式の応用の中でも特に重要なものとして、与えられた整数が素数であるかどうかを判定する問題がある。 もちろん、素数・合成数は整除性に基いて定義されているのだから、合同式と関連があるのは当然であるが、そのような自明なことを超えて、より深い応用が存在する。

フェルマーの小定理によれば $p$ が素数で $a$ が $p$ の倍数ではない整数ならば $a^{p-1}\equiv 1(\mathrm{mod}p)$ である。しかし、以前に述べたように、これだけで与えられた整数 $N$ が素数であるかどうかを判定することはできない。というのは $2^{340}\equiv 1(\mathrm{mod}341)$ のように $N$ が合成数でも $a^{N-1}\equiv 1(\mathrm{mod}N)$ となる場合があるからである。 さらに厄介なことに、 $\gcd (a,N)=1$ となる任意の $a$ に対し $a^{N-1}\equiv 1(\mathrm{mod}N)$ となる合成数 $N$ （カーマイケル数）が存在することも 先に述べた通りである。

一方、ウィルソンの定理は $N$ が素数であることの必要十分条件を与えているが、階乗を計算するための計算量が非常に大きいため、実用的ではない。

しかし、フェルマーの小定理の変形により、特殊な状況においては $N$ が素数であることを比較的簡単に確認できる場合がある。

合同式に基づく素数判定

合成数を法とする剰余類の構造より $a(\mathrm{mod}N)$ の位数は $\lambda (N)$ 以下である。ところで $\lambda (N)\le N-1$ が必ず成立し、かつ等号は $N$ が素数であるとき、そのときに限り成り立つ。 より単純に、フェルマー・オイラーの定理から、$a(\mathrm{mod}N)$ の位数は高々 $\phi (N)$ であるが、やはり $\phi (N)\le N-1$ が必ず成立し、等号は $N$ が素数であるとき、そのときに限り成り立つ。

したがって $\phi (N)=N-1$ は $N$ が素数であるための必要十分条件である。 さらに $N$ が素数であるための必要十分条件は位数 $N-1$ の剰余類が存在することだということがわかる（必要性は原始根の存在から導かれる）。

位数の法則から次の定理が導かれる。

定理 1

$N$ が素数であるための必要十分条件は

$a^{N-1}\equiv 1(\mathrm{mod}N),$

$N-1$ のすべての素因数 $q$ に対して $a^{(N-1)/q}\equiv ̸1(\mathrm{mod}N)$

となる $a$ が存在することである。

この判定法はLucasが発見したもので、合同式に基づく素数判定法の中でも基本的なものである。これを一般化したものがメルセンヌ素数に対するLucas Testである。さて、この判定法は次のように拡張できる。

定理 2

$N$ が素数であるための必要十分条件は、 $N-1$ のすべての素因数 $q$ に対して

$a^{N-1}\equiv 1(\mathrm{mod}N),$

$a^{(N-1)/q}\equiv ̸1(\mathrm{mod}N)$

となる $a$ が存在することである（$a$ は各 $q$ に対して異なっていてもよい）。

証明
$N-1=\prod q_i^{r_i}$ と素因数分解する。各 $q_i$ に対応する $a=a(q_i)$ の位数は $N$ の約数だが $N/q$ の約数ではないので $q_i^{r_i}$ の倍数でなければならない。ということは $\phi (N)$ も $q_i^{r_i}$ の倍数でなければならない。これが各 $q_i$ に対して成り立つことから $\phi (N)=N-1$ である。

さらに、特殊な形の数に対しては $N-1$ の素因数分解を完全に知る必要はない場合がある。最も単純な判定法として、次のものがある。

定理 3

$N=h\cdot 2^n+1$ としたときに $h<2^n$ となっているとする。このとき $N$ が素数であるための必要十分条件は

$a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$

となる $a$ が存在することである（$a$ は各 $q$ に対して異なっていてもよい）。

証明
$N$ が素数で $a$ を原始根とすると原始根の応用例 (1) から上記の式が成り立つから、必要性は成り立つ。

一方 $N$ が合成数であるとすると$N$ の素因数 $p<\sqrt{N}$ がとれる。 ここで $a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$ ならば $p|N|(a^{(N-1)/2}+1)$ より $a^{(N-1)/2}\equiv -1(\mathrm{mod}p)$ も成り立たなければなければならない。 すると $a^{N-1}\equiv 1(\mathrm{mod}p)$ より $a(\mathrm{mod}p)$ の位数は $N-1$ の約数でなければならないが $(N-1)/2$ の約数ではないので $2^n$ の倍数でなければならないことがわかる。よって $p\equiv 1(\mathrm{mod}{2}^n)$ であるが このとき

$N>p^2\ge (2^n+1{)}^2>2^{2n}+1>h\cdot 2^n+1=N$

となり、矛盾が起きる。 よって $a^{(N-1)/2}\equiv -1(\mathrm{mod}N)$ のとき $N$ は素数でなければならない。

この判定法はProthが発見したもので、この形の素数に対する単純な判定法を与えている。そのため、現在知られている巨大な素数の多くは $h\cdot 2^n+1$ の形のものである。

例 $N=7\times 2^{120}+1,a=5$ に対して

$5^{7\times 2^{119}}\equiv -1(\mathrm{mod}7\times 2^{120}+1)$

となるので $7\times 2^{120}+1$ は素数である。

なお、この数 $7\times 2^{120}+1$ の素数性は次のように示すこともできる。

$2^{2^{117}}\equiv -1(\mathrm{mod}7\times 2^{120}+1)$

より $2(\mathrm{mod}7\times 2^{120}+1)$ の位数は $2^{118}$ に一致する。よって位数の法則より、 $7\times 2^{120}+1$ の素因数は $k\cdot 2^{118}+1$ の形でなければならない。ここで $7\times 2^{120}+1$ が合成数と仮定すると

$7\times 2^{120}+1\ge (2^{118}+1{)}^2>2^{236}$

となって矛盾するので $7\times 2^{120}+1$ は素数である。 （上記の事実から、この数はフェルマー数 $F_{117}=2^{2^{117}}+1$ の素因数なので $F_{117}$ が素数ではないこともわかる）