ミラーの判定法(合成数判定)

  暗号等を作成する場合,その数が素数であるか,合成数であるか判定することは重要なことです。そのため素数判定について多くの研究がなされ,現在ではかなり大きな数でも素数かどうか判定することができます。

  最も簡単な方法として,フェルマーの小定理の項で,フェルマーテストについて説明しました。ここでは,それを更に精密化したミラーの判定法(Miller's Test)について説明します。

 
判定法の原理

 ミラーの判定法はフェルマーの小定理

(1) p を素数,xをpで割り切れない整数とする。 このとき,xp-1-1はpで割り切れる。即ち,

p-1 ≡1  (mod p)

が成立する。

と,素数についての次の基本的な性質

(2) p を素数とし,xを,

≡1  (mod p)

を満たす整数とする。このとき,x≡1または-1 (mod p) が成立する。

を基にしています。


 (1)はフェルマーの小定理の項で説明しました。ここでまず(2)を証明しましょう。この性質の証明は素数の基本性質

素数 p が整数の積a×bを割り切れば,aまたはbを割り切る

を使うと簡単です。この性質は,拡張ユークリッドの互除法を使って次の様に示されます。

 上の性質の証明:

 p がa×bを割り切り,p がa を割り切らないとします。このとき,p とa の最大公約数は1です。従って,ユークリッドの互除法から,

cp+da=1

となる整数c,dが存在します。この両辺にbを掛けると,

cpb+dab=b

となります。ここでこの左辺の2つの項はいずれもpで割り切れますから,右辺 b も p で割り切れます。

上の性質を使うと,(2)は次のように証明されます。

(2)の証明:

≡1 (mod p)

とすると,p は

-1=(x-1)(x+1)

を割り切ります。ここで,p は素数でしたから,上の性質から,

pはx-1またはx+1を割り切ります。

従って

x-1≡0 (mod p)または,x+1≡0 (mod p)

となります。これは,

x≡1 (mod p)または-1 (mod p)

を意味します。


ミラーの判定法

 上のことから,整数n>2が素数なら,上の(1),(2)が成立します。従って,(1)または(2)が成立しないような数が見つかれば,nは素数でないことが分かります。そこでn>2に対して次のような操作を行います。

  1. nが奇数であることを確認します。偶数なら,nは合成数です。この場合はこれで終了です。

  2. b=2とします。

  3. n1=n-1とします。

  4. n1 ≡ 1 mod n をチェックします。成立しなければ,フェルマーの判定法で合成数と分かります。この場合はこれで終了です。bn1 ≡ 1 mod nのとき,次に進みます。

  5. n1が偶数のとき(最初は必ず偶数です。),n1=n1/2としします。

  6. n1 ≡ 1 mod n または -1 mod nをチェックします。これ以外の場合は,nが素数であると矛盾です。従ってnは合成数です。この場合はこれで終了です。bn1 ≡ 1 mod n または -1 mod nのとき次に進みます。

  7. n1 ≡ 1 mod n かつ n1が偶数なら5に戻って操作を続けます。

  8. n1 ≡ -1 mod n または n1が奇数なら,bについてのこの操作は終わりです。ここまできた場合,nが合成数か素数かは何も分かりません。

  9. そこで bに1を加えてステップ3に戻って,操作を続けます。

  10. 何度かbを増やして実行しても合成数と判断されないものは,おそらく素数です。


 ミラーの判定法の結論では,幸運ならnが合成数であることは確実に分かりますが,素数であることは恐らくという不確かな結果です。勿論十分沢山のb(実際はn/4個以上)に対して上の操作を実行すれば,合成数か素数か確実に判定できることが示されていますが,あまり多くのbに対して実行するのは現実的ではありません。

 しかし,実際は比較的少ないbについて調べるだけで合成数という判定はかなり可能です。

具体例

n=15841 に対して上の操作を実行してみましょう。b=2 として,

15840≡1 (mod 15841)

ですから,フェルマーの判定法では判定できません。そこで,n1=15840 とし,更にn1=n1/2=7920として,

7920≡1 (mod 15841)

となります。以下指数を順次2で割り,順次計算すると,

3960≡1 (mod 15841),

1980≡1 (mod 15841),

990≡1 (mod 15841),

495≡1 (mod 15841)

となり,指数が奇数になり,b=2では判定できません。

 そこで次に b=3とします。

15840≡1 (mod 15841)

ですから,フェルマーの判定法では判定できません。そこで,n1=15840 とし,更にn1=n1/2=7920として,

7920≡1 (mod 15841)

となります。以下指数を順次2で割り,順次計算すると,

3960≡1 (mod 15841),

1980≡1 (mod 15841),

990≡218 (mod 15841),

となります。これは,x=3990とした場合,x≡1 (mod 15841),であるにもかかわらず,x≡218 (mod 15841)となり,上の性質(2)に反しますから,15841は素数でないことが分かります。

まとめ

  ミラーの判定法は,かなり高速に合成数であることを判定します。(実際フェルマーの判定法で多くのものが既に判定されます。)実際,b=2,3程度でもかなりの合成数を判定してくれます。

例えば,上のアルゴリズムで,b=5まで必要な最小な合成数はどれくらいでしょうか?

ミラーの判定法のプログラムMillerTest.tbtここです。