フェルマーテスト(確率的素数判定アルゴリズム)|Excel VBAで学ぶ数学とアルゴリズム

今回は確率的素数判定アルゴリズムの「フェルマーテスト」について解説していきます。
フェルマーというと『フェルマーの最終定理』で聞いたことがあるという人も多いのではないでしょうか。最終定理という名前で有名なこの定理ですが別名『フェルマーの大定理』とも呼ばれています。

そしてこの大定理と区別するためにあえて”小”と付けられた『フェルマーの小定理』という素数の性質に関した定理も存在しますが、フェルマーテストはこの『フェルマーの小定理』の考えを利用した素数判定アルゴリズムです。(※大定理と小定理は全く持って別のものです)

本ページではこの「フェルマーテスト」のアルゴリズムがどういった仕組みなのかを解説し、最終的にExcel VBAのコードとして実装していきます。

 

フェルマーテストとは

フェルマーテストとは入力された値が素数であるかを判定する、素数判定アルゴリズムです。素数判定アルゴリズムは大きく分けて「決定的素数判定」と「確率的素数判定」の2種類ありますが、このフェルマーテストは『フェルマーの小定理』に基づいた、”確率的”素数判定に属されます。
詳しい説明は後にして、まずはフェルマーテストのアルゴリズムを紹介します。

アルゴリズム自体は非常に単純ですが何故このアルゴリズムでできるのかは少しだけ勉強が必要です。

① パラメータとして、2以上 \(n\) 未満 の自然数 \(a\) を決める 
② \(a\) と \(n\) が「互いに素」(2つの数の最大公約数が1)の場合、 \(n\) は合成数である ⇒ 終了
③「\(a^{n-1} ÷ n\)」の余りが「1」でない場合、 \(n\) は合成数である ⇒ 終了
④「\(a^{n-1} ÷ n\)」の余りが「1」である場合、 \(n\) は素数である”可能性”がある
⑤ \(a\) の値を変更して②~④の判定を指定した回数繰り返す
⑥ 指定回数繰り返してもなお合成数判定が出なければ素数と判定する
  
フェルマーテストは素数判定のアルゴリズムなので、上記の通り「合成数」とわかった時点で処理は終わります。ただこのフェルマーテスト、合成数の判定は確証を持ってできますが素数の判定は100%の確証がありません。これが「確率的素数判定」といわれる所以です。(※詳しくは以降で解説します)

 

『フェルマーの小定理』とは

フェルマーテストのアルゴリズムを理解するには『フェルマーの小定理』を理解する必要があります。
フェルマーの小定理は下記の通りの内容で、素数の性質についての定理です。

―『フェルマーの小定理』とは ―

$$a^{p-1} \equiv 1 (mod \ p)$$

\(p\) が素数で \(a\) と \(p\) が「互いに素」の自然数の場合、上記の式が成立する。
式の意味は「\(a^{p-1}\) を \(p\) で割った時の余りは1である」

「互いに素」とは、2つの数を共に割り切ることのできる整数が「1」のみである、つまりは2つの数の最大公約数が「1」であるもののことをいいます。

たとえば「3」と「10」の場合、共に割り切ることのできる整数は「1」だけなので、この2つの数は互いに素であるといえます。逆に「5」と「10」の場合、共に「5」で割り切ることができるのでこの2つの数は互いに素ではありません。

 
『フェルマーの小定理』の対偶を利用したアルゴリズム

フェルマーテストは上記の『フェルマーの小定理』の対偶を利用して素数を判定するアルゴリズムです。対偶とは「AならばB」を「BでないならばAでない」というように前提と結論を否定にして両者を逆転させたもののことをいいます。

フェルマーの小定理の対偶は下記のような内容になります。

―『フェルマーの小定理』の対偶 ―

$$ a^{n-1} ≢ 1 (mod \ n) $$

\(a\) と \(n\) が「互いに素」の自然数の場合、上記の式を満たせば \(n\) は素数ではない。
式の意味は「\(a^{n-1}\) を \(n\) で割った時の余りは1ではない」

このようにフェルマーの小定理の対偶を考えることで \(n\) の値が”素数ではない”ということを判定することができます。

ただ、ここで注意しないといけない点は「\(a^{n-1} ÷ n\)」の余りが「1」であるからといって素数であるとは必ずしもいえないということです。フェルマーの小定理の対偶はあくまでも”素数ではない”ということがわかるだけです。つまり、「\(a^{n-1} ÷ n\)」の余りが「1」であったとしてもそれは素数であるかもしれないし素数ではないかもしれないという訳です。

ここでフェルマーテストではもう1つの自然数 \(a\) の値に注目します。
\(a\) の値は \(n\) と互いに素となる自然数という縛り以外は何もありません。そこでこの条件を満たす範囲内で \(a\) の値をランダムに変化させていきます。このとき、指定の回数(たとえば100回)だけ値を変更したとき常に「\(a^{n-1} ÷ n\)」の余りが「1」であればそれは素数であると判定しようという確率的な判定を行います。(※ \(a\) の値の変更回数が多いほど素数の判定精度はよくなります)

このような確率的に判定された素数のことを「確率的素数」といい、確率的素数を使って素数判定を行うアルゴリズムのことを「確率的素数判定アルゴリズム」といいます。これに対して100%素数を判定するようなアルゴリズムのことは決定的素数判定アルゴリズムといいます。

必ず素数が判定できるなら決定的アルゴリズムだけ使えばいいと思う人も多いと思いますが、決定的素数判定は確率的素数判定に比べてかなりの処理時間を必要とします。そのため、処理の高速な確率的素数判定の判定精度を上げて決定的素数判定の代わりに使われるケースも多いです。

ちなみに、判定精度に関わる \(a\) はランダム性を出すために乱数扱いとなりますが、このようにアルゴリズム内で乱数を使うようなもののことを「乱択アルゴリズム」ともいいます。乱択アルゴリズムについては「モンテカルロ法」も合わせて参照下さい。

  
カーマイケル数(絶対擬素数)

フェルマーテストによって求められた素数は「確率的素数」といいますが、その中でも誤って素数として判定されてしまった合成数のことは「擬素数」といいます。

フェルマーテストは判定する回数を増やせば増やすほど精度を上げて素数を判定することができます。
しかし、ある一定の数に対しては何回判定しても素数と判定されてしまう合成数が存在します。

このような、「\(a^{n-1} ÷ n\)」の「\(a\)」の数値をいくら変えても素数と判定されてしまう合成数のことを「カーマイケル数」もしくは「絶対擬素数」といい、無限に存在していることがわかっています。

つまりこのカーマイケル数が存在するとわかった時点で、同時にフェルマーテストでの完全な素数判定はできないということもわかっています。

 

サンプルコード

フェルマーテストをVBAで書くと下記の通りです。

本コードでは「互いに素」なのかを確認するため、「ユークリッドの互除法」という2つの数の最大公約数を求めるアルゴリズムを利用しています。

また、フェルマーテストのアルゴリズムは上記の内容で完結していますが、フェルマーの小定理の対偶を確認するコードとして「modBignum.Bignum_ModExp(a, n-1, n)」というよくわからない関数が存在していると思います。この関数は引数として「基数[a],指数[n-1],除数[n]」の順に数値を入れたら「\(a^{n-1} ÷ n\)」の余りを返す関数ということだけわかっていれば大丈夫です

なぜこのような関数を挟むかというと、単純にVBAで「a ^ (n-1) Mod n」と書くと入力された数値が2桁になるだけでオーバーフローを起こすためです。そのため、オバーフローを起こさないような仕組みで計算が行えるBignum_ModExp関数を使い「\(a^{n-1} ÷ n\) 」の余りを求めています。
もしオーバーフローを起こさないのであれば「a ^ (n-1) Mod n」という書き方で問題ありません。

※上記コードをコピペして実行する際はBignum_ModExp関数のコードも必要になります。
「modBignum」という名称の新規標準モジュールを作成し下項目のコードをコピペしてください。
 

巨大桁数演算 (Bignum_ModExpについて)

VBAにおいてべき乗の計算は非常に厄介です。
というのも「\(a^n\)」のような簡単な数式に対して「\(a\)=10」「\(n\)=10」のような小さい数値を入れたとしてもその計算結果は「10,000,000,000」と非常に膨大な数になりすぐにオーバーフローを起こしてしまうためです。

そんなオーバーフローを回避する方法として”文字列”を使うといった手法があります。
下記リンクのサイトではそんな仕組みを使った巨大桁数の計算のサンプルコードが公開されています。

 
下記のコードは全て上記リンクのサイト様より拝借したものです。
よってコードの詳細はリンク先を参照してください。
非常に長いコードですがフェルマーテストのアルゴリズムだけ理解できればいいという場合は、このコードで何をしているのかを理解する必要は一切ありません

 

まとめ

今回は素数判定アルゴリズムの「フェルマーテスト」の解説でした。
フェルマーテストのアルゴリズムは下記の通りです。

① パラメータとして、2以上 \(n\) 未満 の自然数 \(a\) を決める。 
② \(a\) と \(n\) が「互いに素」(2つの数の最大公約数が1)の場合、 \(n\) は合成数である。 ⇒ 終了
③「\(a^{n-1} ÷ n\)」の余りが「1」でない場合、 \(n\) は合成数である。⇒ 終了
④「\(a^{n-1} ÷ n\)」の余りが「1」である場合、 \(n\) は素数である”可能性”がある。
⑤ \(a\) の値を変更して②~④の判定を指定した回数繰り返す。
⑥ 指定回数繰り返してもなお合成数判定が出なければ素数と判定する。

フェルマーテストはいわゆる確率的素数を求めるアルゴリズムなので、運が悪いと合成数でも素数として判定されてしまうことがあります。

このフェルマーテストは素数判定アルゴリズムのはしりであり、以降に改良版の素数判定アルゴリズムとして「ミラーラビン素数判定法」や「AKS素数判定法」といったものが誕生しています。

特に「AKS素数判定法」は”確率的”素数ではなく決定的に素数を判定することが可能になった、世界初の素数判定アルゴリズムといわれています。興味があればぜひこれらのアルゴリズムも勉強してみて下さい。

 
 icon-book オススメ書籍

Excel, VBA, アルゴリズム, 数学

Posted by Lic