与えられた奇数 n が素数であるかどうかを高速に判定することはなかなか難しいが,比較的高速な判定法に,Miller-Rabin テストと呼ばれるものがある.

次のように,ブール関数 Suspect(b, n) をまず定義する.b は基底を表す整数,n は奇数.

Function Suspect(b, n), where b is an integer that is called the base, and n is an odd integer. It returns one of the boolean values TRUE or FALSE.

  • Let t be the highest power of 2 so that 2t devides n-1 and u be the biggest odd integer that devides n-1.
    This means we can write n-1 = 2tu.

  • Let x0 be bu mod n.
  • For all i from 1 to t, let xi be (xi-1)2 mod n.
  • If, for any i from 1 to t, xi = 1 and xi-1 <> 1 and xi-1 <> n-1, then return FALSE.
  • else, if xt <> 1, then return FALSE.
  • else return TRUE.

関数の値がFALSE であれば,n は素数でないことは直ちに言えるが,一方,関数の値がTRUE の場合には,極まれに n は素数でないこともある.

しかし,異なる基底で複数回計算し,それぞれの関数値がすべてTRUEであれば,素数であることが保証されることも知られている.

具体的に,1000000(百万)までの 奇数 n については,Suspect(2, n) と Suspect(3, n) とで計算した関数の値が両方とも TRUE であれば,n が素数であることが保証されている.

さらに,すべての32ビット 奇数 n (つまり, n < 232) までに拡大したければ,Suspect(2, n), Suspect(7, n) および Suspect(61, n) の3つの異なる基底で計算した関数値が すべてTRUE であれば,n が素数であることが保証されていることを利用すればよい.

以下はC言語プログラム.

unsigned long long calc_pow(int a, unsigned k, unsigned n)
{
    unsigned long long p;
    unsigned bit;
p = 1; for (bit = 0x80000000U; bit > 0; bit >>= 1) { if (p > 1) p = (p*p) ; if (k & bit) p = (p*a) ; } return p; }
int suspect(int b, unsigned n) { unsigned i; unsigned t, u; unsigned long long x0, x1;
u = n-1; t = 0; while ((u & 1) == 0) { t++; u >>= 1; } x0 = calc_pow(b, u, n); for (i = 1; i <= t; i++) { x1 = (x0*x0) ; if (x1 == 1 && x0 != 1 && x0 != n-1) return 0; x0 = x1; } return x1 == 1; }
int prime_test(unsigned n) { if (n <= 1) return 0; /* 0, 1 */ if (n == 2) return 1; /* 2 */ if (n == 3) return 1; /* 3 */ if ((n & 1) == 0) return 0; /* other even integers */
if (n <= 1000000) { if (!suspect(2, n)) return 0; if (!suspect(3, n)) return 0; } else { if (!suspect(2, n)) return 0; if (!suspect(7, n)) return 0; if (!suspect(61, n)) return 0; } return 1; }

上記のプログラムでは,
  calc_pow 関数は ak mod n を計算する.
  最後の prime_test 関数 は任意の32ビット内の整数について,それが素数であるかどうかを判定する.

繰り返しになるが,Suspect関数を1つだけ使って素数判定すると間違った結果を出すこともあるが,異なる基底を組み合わせて複数回計算するば,素数判定は正しくできる.

計算時間もかなり高速だと思われます.

<メモ>
本記事は オンラインプログラムコンテスト問題 10956 Prime Suspect による.

Comments are closed.

Post Navigation