15.7.1 素数テスト

mpz_probab_prime_p (see Number Theoretic Functions)で行っている素数テストは， 最初に小さい因数でお試し的に除算を行い，しかる後に Miller-Rabin 確率的素数テストアルゴリズムを行います。これはKnuth本の 4.5.4 algorithm P (see References)に解説されている方法です。

入力値nが奇数で，奇数nを用いてn = q*2^k+1と表現できるならば， このアルゴリズムは乱数xを選び， x^q mod n が 1 か -1, もしくは，x^(q*2^j) mod n が 1かどうかを 1<=j<=kに対して確認します。このどれかに当て嵌まるのであれば，nは素数である確率が高く，あてはまらないのであれば，nは素数に非ずと断言できます。

任意の素数nはこのテストを必ずパスしますが，素数でないものも幾つかはパスしてしまいます。 このような非素数をベースxの強い偽素数（strong pseudoprimes）と呼びます。強い偽素数が存在する確率が1/4以上になるnは存在していません(Knuth exercise 22参照)ので，xをランダムに選ぶと，「確率的素数」が非素数であるような確率は1/4未満に抑えられます。

実際，強い偽素数は滅多に存在しておらず，解析的に知られている以上にこのテストは強力です。1/4は任意のnに対して調べられたうち最大の確率です。