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

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

　

判定法の原理

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

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

を基にしています。

　（１）はフェルマーの小定理の項で説明しました。ここでまず（２）を証明しましょう。この性質の証明は素数の基本性質

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

上の性質を使うと，（２）は次のように証明されます。

　上のことから，整数ｎ＞２が素数なら，上の（１），（２）が成立します。従って，（１）または（２）が成立しないような数が見つかれば，ｎは素数でないことが分かります。そこでｎ＞２に対して次のような操作を行います。

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

2. ｂ＝２とします。

3. ｎ１＝ｎ－１とします。

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

5. ｎ１が偶数のとき（最初は必ず偶数です。），ｎ１＝ｎ１/２としします。

6. ｂ^ｎ１ ≡ １ mod ｎ　または －１ mod ｎをチェックします。これ以外の場合は，ｎが素数であると矛盾です。従ってｎは合成数です。この場合はこれで終了です。ｂ^ｎ１ ≡ １ mod ｎ　または －１ mod ｎのとき次に進みます。

7. ｂ^ｎ１ ≡ １ mod ｎ かつ ｎ１が偶数なら５に戻って操作を続けます。

8. ｂ^ｎ１ ≡ -１ mod ｎ または ｎ１が奇数なら，ｂについてのこの操作は終わりです。ここまできた場合，ｎが合成数か素数かは何も分かりません。

9. そこで　ｂに１を加えてステップ３に戻って，操作を続けます。

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

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

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

ｎ＝15841 に対して上の操作を実行してみましょう。ｂ＝２　として，

２^{１５８４０}≡１ （mod １５８４１)

ですから，フェルマーの判定法では判定できません。そこで，ｎ１＝１５８４０　とし，更にｎ１＝ｎ１/２＝７９２０として，

２^７９２０≡１ （mod １５８４１)

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

２^３９６０≡１ （mod １５８４１)，

２^１９８０≡１ （mod １５８４１)，

２^９９０≡１ （mod １５８４１)，

２^４９５≡１ （mod １５８４１)

となり，指数が奇数になり，ｂ＝２では判定できません。

　そこで次に　ｂ＝３とします。

３^{１５８４０}≡１ （mod １５８４１)

ですから，フェルマーの判定法では判定できません。そこで，ｎ１＝１５８４０　とし，更にｎ１＝ｎ１/２＝７９２０として，

３^７９２０≡１ （mod １５８４１)

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

３^３９６０≡１ （mod １５８４１)，

３^１９８０≡１ （mod １５８４１)，

３^９９０≡２１８ （mod １５８４１)，

となります。これは，ｘ＝３^９９０とした場合，ｘ^２≡１ （mod １５８４１)，であるにもかかわらず，ｘ≡２１８ （mod １５８４１)となり，上の性質（２）に反しますから，１５８４１は素数でないことが分かります。

　 ミラーの判定法は，かなり高速に合成数であることを判定します。（実際フェルマーの判定法で多くのものが既に判定されます。）実際，ｂ＝２，３程度でもかなりの合成数を判定してくれます。

例えば，上のアルゴリズムで，ｂ＝５まで必要な最小な合成数はどれくらいでしょうか？

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