初等整数論/合同式に基づく素数判定のソースを表示

{{Nav}}

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

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

一方、[[初等整数論/フェルマーの小定理#ウィルソンの定理|ウィルソンの定理]]は <math>N</math> が素数であることの必要十分条件を与えているが、階乗を計算するための計算量が非常に大きいため、実用的ではない。


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


== 合同式に基づく素数判定 ==
[[初等整数論/合成数を法とする剰余類の構造|合成数を法とする剰余類の構造]]より <math>a\pmod{N}</math> の位数は <math>\lambda(N)</math> 以下である。ところで <math>\lambda(N)\leq N-1</math> が必ず成立し、かつ等号は <math>N</math> が素数であるとき、そのときに限り成り立つ。
より単純に、[[初等整数論/合成数を法とする合同式#フェルマー・オイラーの定理|フェルマー・オイラーの定理]]から、<math>a\pmod{N}</math> の位数は高々 <math>\varphi(N)</math> であるが、やはり
<math>\varphi(N)\leq N-1</math> が必ず成立し、等号は <math>N</math> が素数であるとき、そのときに限り成り立つ。

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


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

====== 定理 1 ======
<math>N</math> が素数であるための必要十分条件は
:<math>a^{N-1}\equiv 1\pmod{N},</math>
:<math>N-1</math> のすべての素因数 <math>q</math> に対して <math>a^{(N-1)/q}\not\equiv 1\pmod{N}</math>
となる <math>a</math> が存在することである。

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

====== 定理 2 ======
<math>N</math> が素数であるための必要十分条件は、 <math>N-1</math> のすべての素因数 <math>q</math> に対して
:<math>a^{N-1}\equiv 1\pmod{N},</math>
: <math>a^{(N-1)/q}\not\equiv 1\pmod{N}</math>
となる <math>a</math> が存在することである（<math>a</math> は各 <math>q</math> に対して異なっていてもよい）。

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


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

====== 定理 3 ======
<math>N=h\cdot 2^n+1</math> としたときに <math>h<2^n</math> となっているとする。このとき <math>N</math> が素数であるための必要十分条件は
:<math>a^{(N-1)/2}\equiv -1\pmod{N}</math>
となる <math>a</math> が存在することである（<math>a</math> は各 <math>q</math> に対して異なっていてもよい）。

'''証明'''<br />
<math>N</math> が素数で <math>a</math> を原始根とすると[[初等整数論/原始根と指数#原始根の応用例|原始根の応用例 (1)]] から上記の式が成り立つから、必要性は成り立つ。

一方 <math>N</math> が合成数であるとすると<math>N</math> の素因数 <math>p<\sqrt{N}</math> がとれる。
ここで <math>a^{(N-1)/2}\equiv -1\pmod{N}</math> ならば <math>p | N | (a^{(N-1)/2}+1)</math> より <math>a^{(N-1)/2}\equiv -1\pmod{p}</math> も成り立たなければなければならない。
すると <math>a^{N-1}\equiv 1\pmod{p}</math> より <math>a\pmod{p}</math> の位数は <math>N-1</math> の約数でなければならないが <math>(N-1)/2</math> の約数ではないので
<math>2^n</math> の倍数でなければならないことがわかる。よって <math>p\equiv 1\pmod{2^n}</math> であるが
このとき
:<math>N>p^2\geq (2^n+1)^2>2^{2n}+1>h\cdot 2^n+1=N</math>
となり、矛盾が起きる。
よって <math>a^{(N-1)/2}\equiv -1\pmod{N}</math> のとき <math>N</math> は素数でなければならない。


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

'''例''' <math>N=7\times 2^{120}+1, a=5</math> に対して
:<math>5^{7\times 2^{119}}\equiv -1\pmod{7\times 2^{120}+1}</math>
となるので <math>7\times 2^{120}+1</math> は素数である。

なお、この数 <math>7\times 2^{120}+1</math> の素数性は次のように示すこともできる。
:<math>2^{2^{117}}\equiv -1\pmod{7\times 2^{120}+1}</math>
より <math>2\pmod{7\times 2^{120}+1}</math> の位数は <math>2^{118}</math> に一致する。よって位数の法則より、 <math>7\times 2^{120}+1</math> の素因数は <math>k\cdot 2^{118}+1</math> の形でなければならない。ここで <math>7\times 2^{120}+1</math> が合成数と仮定すると
:<math>7\times 2^{120}+1\geq (2^{118}+1)^2>2^{236}</math>
となって矛盾するので <math>7\times 2^{120}+1</math> は素数である。
（上記の事実から、この数はフェルマー数 <math>F_{117}=2^{2^{117}}+1</math> の素因数なので <math>F_{117}</math> が素数ではないこともわかる）

{{Nav}}

{{DEFAULTSORT:しよとうせいすうろん こうとうしきにもとつくそすうはんてい}}
[[Category:初等整数論|こうとうしきにもとつくそすうはんてい]]