カーマイケル数
フェルマ・テストを不完全たらしめている原因はカーマイケル数です。
Def.11 $\gcd(b,n)=1$ を満たす全ての整数 $b$ に対して
$b^{\,n-1} \equiv 1 \pmod{n}$
が成り立つ合成数 $n$ をカーマイケル数と呼ぶ。
Ex.12 $n=561=3 \times 11 \times 17$ はカーマイケル数である。
証明 $\gcd(b,561)=1$ であれば、フェルマの小定理より
\begin{align}
b^{2} &\equiv 1 \pmod 3, \\
b^{10} &\equiv 1 \pmod{11}, \\
b^{16} &\equiv 1 \pmod{17} \\
\end{align}
となります。それぞれ、$280$ 乗、$56$ 乗、$35$ 乗すると
\begin{align}
b^{560} &\equiv 1 \pmod 3, \\
b^{560} &\equiv 1 \pmod{11}, \\
b^{560} &\equiv 1 \pmod{17} \\
\end{align}
となり、
$b^{560}-1$ は $3$, $11$, $17$ の公倍数ですから
$b^{\,560} \equiv 1 \pmod{561}$.
(証明終)
次の定理を使うと大きなカーマイケル数を作ることができます。
Th.13 $p=6k+1$, $q=12k+1$, $r=18k+1$ が全て素数であれば $n=p \times q \times r$ はカーマイケル数である。
証明は
Ex.12 と全く同じです。
Ex.14
k = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271609318291
のとき
p = 6k + 1 = 13438468453066825263344653683410665668729872983407897209399934605782751227080965672285264959629655909747
q = 12k + 1 = 26876936906133650526689307366821331337459745966815794418799869211565502454161931344570529919259311819493
r = 18k + 1 = 40315405359200475790033961050231997006189618950223691628199803817348253681242897016855794878888967729239
は全て素数で
n = pqr = 14561314392384758852607372045391100342305613529432683239147836573776346740245578013749386663115053375527637666588629193151550389687696379599004671655261602333117349735165428436344922950761580622183044886774735262914257003709862150465768021078578761491289686266731268838123191809245649371909369818627048924845769
は 1031 ビットのカーマイケル数。
Rem.15 $b^{n-1} \,\%\, n$ は $\gcd(b,n)$ の倍数です。
ですから、カーマイケル数 $n$ が小さい素因数 $r$ を持っていれば、
フェルマ・テストで底 $b$ をランダムに取れば少なくない確率で
$b$ は $r$ の倍数となり
$b^{n-1} \,\%\, n \neq 1$
となって $n$ を合成数だと見破ることができます。
ところが Ex.14 のように素因子が巨大なカーマイケル数では、フェルマ・テストで合成数だと見破ることは絶望的です。
Rem.16 厄介者のカーマイケル数は無限個存在することが証明されています。
しかし幸いなことに、そんなにたくさんはありません。
Rem.17 カーマイケル数も合成数だと見破ることのできる確率的素数判定法としては
などがあります。
ミラー・ラビン法は今迄の本講義の知識で理解できますがそこそこ複雑です。
ソロベイ・ストラッセン法を理解するには「平方剰余」の知識が必要となります。
Rem.18 1729 は
タクシー数
として有名な数ですが、実はカーマイケル数でもあります。