与えられた奇数 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言語プログラム.

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

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

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

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

Comments are closed.

Post Navigation