projectpn
projectpn

フェルマーの小定理

pが素数で、aがaとpが互いに素であるような自然数であるとき、
a^{p-1}\equiv 1 \pmod{p}
が成り立つ。(aのp-1乗をpで割ったあまりが1になるという意味)(証明略)

フェルマーテスト

フェルマーの小定理の対偶を用いると、
a^{n-1}\not \equiv 1 \pmod{n}
であるとき、nは合成数であると言える。a^{n-1}\equiv 1 \pmod{n}が成り立つとき、nはおそらく素数であると考えられる。このようなnを確率的素数という。
入力:素数判定する数 n
出力:合成数だとわかれば「nは合成数である」、わからなければ「nは確率的素数である」と出力する。
動作
ステップ1
2以上n未満の自然数からランダムに1つ数字を選び、aとする。
ステップ2
nとaの最大公約数が1でないとき、「nは合成数である」と出力して終了する。
ステップ3
\scriptstyle{a^{n-1}\not \equiv 1 \pmod{n}}であれば、「nは合成数である」と出力して終了する。
そうでないとき、「nは確率的素数である」と出力して終了する。
これを何度も実行して、たくさんのaで調べることによってnが素数であるかどうかをかなりの精度で調べることができる。

累乗剰余の求め方

\scriptstyle{a^{n-1} \pmod{n}}を普通の方法で計算すると、n-2回の乗算と1回の剰余算が必要となってしまう。また、nが大きくなるにつれ\scriptstyle{a^{n-1}}の値が爆発的に大きくなってしまい、乗算が大変になる。しかし、バイナリ法と呼ばれるアルゴリズムを用いることで効率的に累乗剰余を求めることができる。
\scriptstyle{{\rm powmod}(a,b,m):}
入力:底 a, 指数 b, 法 m(ただし、a > m)
出力:\scriptstyle{a^b \bmod m}
動作
ステップ1
b=1のとき、aを出力する
ステップ2
\scriptstyle{c={\rm powmod}(a,\lfloor \frac{b}{2} \rfloor,m)}とする。
ステップ3
bが偶数のとき、\scriptstyle{c^2 \bmod m}を出力する。
bが奇数のとき、\scriptstyle{c^2\times a \bmod m}を出力する。

カーマイケル数の存在

しかし、任意のnと互いに素なaに対してフェルマーテストを通過してしまうカーマイケル数と呼ばれる合成数が無限個存在する。
また、効率的に与えられた数がカーマイケル数であるかを判定する方法は知られていない。
そのため、純粋な素数判定目的でフェルマーテストを用いるべきでない。

「フェルマーテスト」をウィキ内検索
最終更新：2012年07月03日 18:28