数が素数かどうか判定する
素数判定は、数が素数かどうかを確定します。試し割り、Miller-Rabin、決定的判定法を学びましょう。
- 1
素数判定:試し割り(sqrt(n) までの素数で割れるか確認。大きな n では遅い)、Fermat(a^(n-1) ≡ 1 mod n。カーマイケル数にだまされる)、Miller-Rabin(確率的、高速、広く使用)、AKS(決定的、多項式時間、ただし実際には遅い)、BPSW(確率的、反例は知られていない)。暗号用途では、40 ラウンド以上の Miller-Rabin が標準です。
- 2 素数判定ツール →
数の素数判定を行います。ツールは複数ラウンドの Miller-Rabin を使います。小さな数(< 2^64)では決定的なチェックを使います。大きな数では、結果は「おそらく素数」で、誤り確率は 2^-80 未満です(十分なラウンド数で)。
- 3 約数計算ツール →
数が合成数なら、素因数分解して素因数を確認します。これにより素数判定の結果が裏付けられます。合成数は 1 と自分以外の約数を持ちます。大きな数では、素因数分解は素数判定よりはるかに難しいです(RSA セキュリティの基礎)。
よくある質問
- Miller-Rabin は誤ることがありますか?
- Miller-Rabin は確率的です。合成数が各ラウンドを通過する確率は高々 1/4 です。40 ラウンドなら、誤り確率は (1/4)^40 ≈ 10^-24 です。実用上、誤ることはありません。3.3×10^24 未満の数で決定的な結果を得るには、特定の底(2、3、5、7、11、13、17、19、23、29、31、37)でのテストで十分です。
- なぜ AKS テストを使わないのですか?
- AKS は決定的で多項式時間です(理論的に重要)。ただし、実際には Miller-Rabin よりはるかに遅く、定数因子が大きいです。実用アプリケーションでは、十分なラウンドの Miller-Rabin が好まれます。速く、誤り確率も無視できるほど小さいからです。