確率的素数判定 - ei1333の日記

昔ツイートした方法をふと思い出しました

確率的アルゴリズム

決定的なアルゴリズムとは異なり、ランダム性を取り入れた確率的アルゴリズム（乱択アルゴリズム）を用いることで、効率的に計算できるようになる場合があります。

確率的アルゴリズムでは、計算時間がかかる場合や誤った判定をする場合などが無視できるほど低い確率であることを保証しており、決定的アルゴリズムと比較して効率的に計算することが可能です。

単純な決定的な素数判定アルゴリズムとして ${\Theta(\sqrt N)}$ の試し割りする方法があります。

${N}$ が与えられたときに、 ${N}$ が ${2}$ 以上 ${\sqrt N}$ 以下の整数で割り切れるかどうかを判定します。

template< typename T >
bool is_prime(T N) {
  for(T i = 2; i * i <= N; i++) {
    if(N % i == 0) return false;
  }
  return true;
}

より効率的な方法として、AKS 素数判定法と呼ばれる ${\tilde{O}(\log(n)^{7.5})}$ の決定的アルゴリズムを用いる方法も存在します。

単純な確率的素数判定アルゴリズムを紹介します。

常に素数ではないと判定すればよいです。

template< typename T >
bool is_prime(T N) {
   return false;
}

素数定理を用いてランダムに選んだ ${N}$ が素数である確率は ${\frac {1} {\log {N}}}$ に近似できます。

つまり正しい素数判定をする確率は ${1 - \frac {1} {\log {N}}}$ に近似します。

このアルゴリズムは、実装が簡潔であり与えられる ${N}$ が大きいほど正しく動作する確率が高くなる利点があります。(いや　これ間違える確率を無視できねえな）

うし