フェルマー・テスト - memotic forgotten

素数判定法。素因数分解をしなくても素数でないことを証明できる。

オイラーの定理

「またオイラーか」のオイラー。どうせ証明載せるなら一般化されたものにしよう、ということでこちらを先に紹介。フェルマーの小定理はこれの特殊例。

$a^{%5Cphi(n)}%5Cequiv 1%5Cpmod{n}$
が $n$ と互いに素な自然数 $a$ について成り立つ。

$%5Cphi(n)$ は、 $n$ と互いに素な $n$ 以下の自然数の個数を表す関数で、オイラー関数とか呼ばれている。

証明

$n$ と互いに素な数を順番に $x_1, x_2, %5Cdots, x_{%5Cphi(n)}$ とする。 $a$ も互いに素だから、これら $x_i$ に $a$ をかけた数も $n$ と互いに素に違いないし、どれか二つが合同なんてこともない。ということは、すべての $ax_i$ はどれかの $x_j$ に対応するはずだから、 $%5Cprod^{%5Cphi(n)}ax_i%5Cequiv %5Cprod^{%5Cphi(n)} x_j%5Cpmod{n}$ となるはずである*1。あとは両辺を $%5Cprod^{%5Cphi(n)} x_i$ で割ればいい、はず。

フェルマーの小定理

$p$ が素数ならば、
$a^{p-1}%5Cequiv 1%5Cpmod{p}$
が $p$ と互いに素な自然数 $a$ について成り立つ。

さっきも言ったように、オイラーの定理の特殊な場合。 $p$ が素数ならば、 $%5Cphi(p)=p-1$ になる。
どうでもいいが、フェルマーの小定理をFLTと略すのはやめたほうがいいと思うな。せっかく最終定理と混同しないように「小定理」って名前にしたのに最終定理もFLTじゃん。

対偶

$p$ と互いに素な自然数 $a$ について、
$a^{p-1}%5Cnot%5Cequiv 1%5Cpmod{p}$
ならば、 $p$ は素数ではない。

フェルマー・テストと擬素数

というわけで、この対偶は確率的素数判定法として利用できる。「確率的」なのは、要するにフェルマー・テストをパスする合成数が存在するということである。たとえば、341=11*31について「底」 $a=2$ のときを考えると、 $2^{341-1}%5Cequiv 1%5Cpmod{341}$ である。このとき、341を「底2に対する擬素数」と呼ぶ。
ありがたいことに、 $3^{341-1}%5Cequiv 56%5Cpmod{341}$ であるから、341が素数でないことは証明できる。

カーマイケル数

ならば、 $p$ と互いに素な数全部でテストをすればいいのかというと、非常に残念なことにそうでもない。それゆえ「確率的」なのだが、たとえば561=3*11*17は、互いに素なすべての $a$ を底としたフェルマー・テストをパスする。こういう数をカーマイケル数と言い、誠に遺憾ながら無限に存在することが知られている。

でも安心して

まぁ、カーマイケル数なんて、そうそうあるもんでもないから、複数の底についてテストすればだいたいの合成数は弾けるので、便利。

あと

今夜覚えてたらミラー・ラビン・テストについて書く
(追記)やめた。mendoxai.

*1:記号の使い方に自信がない