Fermatテストというのは、Fermatの小定理を用いて 素数判定をする方法だが、これがなかなか面白い。 Fermatの小定理というのは、nが素数のときnより小さいaについて、 aのn乗をnで割ったあまりがaになるというあれで、 もし素数でなければこの関係が成り立つ確率は低いので、 それなりに素数判定ができるというわけだ。
ところで、Fermatテストに失敗すれば直ちにそれは素数ではないとわかるが、 成功したとしても素数ではない可能性もある。 繰り返しFermatテストをすることで限りなく確率をあげることが できるのだろうか。 実はその答えは否である。 素数ではないのに、すべてのaに対してFermatテストが成功してしまう Carmichael数というのが存在するのだ。 つまり、Fermatテストは正しい素数判定法ではないのだ。
ここで何が面白いかというと、 Fermatテストが正しくない確率、 つまり、Carmichael数に出くわす確率というのが、 宇宙線によってコンピュータが誤動作する確率よりも低いということだ。