フェルマーテスト - crypto-writeup-public

確率的素数判定法の一つ

Fermat's little theorem: 素数 $p$ と互いに素な $a$ → $a^{p-1} \equiv 1 \mod p$

対偶を取ると

$p$ と互いに素な $a$ → $a^{p-1} \not\equiv 1 \mod p$ なら $p$ は素数でない

ということで、判定したい値 $n$ に対して適当に $a < n$ を持ってきて

と判断できる。 $a^{n-1} \equiv 1 \mod n$ のとき、そうなったのは $n$ が素数だからなのか、たまたまそうなったのかはわからないが、様々な $a$ に対して繰り返し判定を行うことで、精度を高めることができる

ところで、フェルマーテストを確実に通過する合成数カーマイケル数もある