素数判定プログラム3 C言語GMPライブラリの続きです。

今までとは違った素数判定プログラムを書いていきます。

前回のgmpプログラムではmpz_probab_prime_p　関数を使いました。

実行すると計算が一瞬で終わります。一体どういう仕組みなのでしょうか。

mpz_probab_prime_p 関数は内部でMiller_Rabin 素数テストを行っています。

では、Miller Rabin素数テストとは何かを調べていきましょう。

Miller Rabin素数テストはフェルマーテストを改良して作られたものです。

というわけでまずはフェルマーテストの説明から。


nが素数の場合、

a ^ (n - 1) ≡ 1 (mod n)

が成立します。　a　については 1 <= a < n　という条件がついています。　ま、そりゃそうです。

aについては単純にa = 2 と置き換えて問題ありません。

上の式を変換すると

2 ^ (n - 1 ) mod n = 1

計算結果が1となると素数と判定します。

素数3の場合 2 ^ 2= 4,  4 % 3 = 1

素数5の場合 2 ^ 4 = 16, 16 % 5 = 1

素数7の場合 2 ^ 6 = 64, 64 % 7 = 1

素数の場合は必ず計算結果の余りが1　となります。これがフェルマーテストです。

1にならない場合は素数ではないので弾くことができます。

ところが素数でない場合も1　となることがあります。

341 = 11 * 31　は素数ではありませんが2となります。 

(2 ^ 340) % 341 = 1

前回までのプログラムは素数かどうかを割り算をして割り切れるかどうかを調べました。

フェルマーテストの場合は乗数計算となります。

しかも数が爆発します。

41が素数かどうかを調べるには 2 ^ 40です。計算すると1099511627776 になります。

2を40回掛け算しなければいけません。

これは大変、ということで簡単にするアルゴリズムがあります。

繰り返し二乗法です。

素数判定法5 繰り返し二乗法に続きます。