Spaghetti Source logo

確率的素数判定

説明

Millar-Rabin Test によって与えられた数 n が素数かどうかを判定する.確率的とは言っているが,扱う数を 2^32 程度に限り,アルゴリズムをデランダマイズドしているため,コメントに記述されている領域に関してはこのアルゴリズムは厳密に素数判定を行う

2^16 程度の数に対して素数判定を行うには,このアルゴリズムはそれほど効率的でない (エラトステネスのふるいなどで素数を生成し,試し割るほうがよい).ところが,2^24 を超える数を前述の方法で判定しようとすると素数生成で絶望するため,このアルゴリズムを使うことになる.

計算量

ループの回数はほとんどの数に対して 200 回程度である.

使い方

bool isPrime(Int n)
数 n が素数ならば true, そうでなければ false

ソースコード

bool suspect(Int a, int s, Int d, Int n) {
  Int x = powMod(a, d, n);
  if (x == 1) return true;
  for (int r = 0; r < s; ++r) {
    if (x == n - 1) return true;
    x = x * x % n;
  }
  return false;
}
// {2,7,61,-1}                 is for n < 4759123141 (= 2^32)
// {2,3,5,7,11,13,17,19,23,-1} is for n < 10^16 (at least)
bool isPrime(Int n) {
  if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
  int test[] = {2,3,5,7,11,13,17,19,23,-1};
  Int d = n - 1, s = 0;
  while (d % 2 == 0) ++s, d /= 2;
  for (int i = 0; test[i] < n && test[i] != -1; ++i)
    if (!suspect(test[i], s, d, n)) return false;
  return true;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.15 23:39:53.