PHPで巨大素数の生成と判定

「PHPで素数かどうか判定」ではPHPの整数型で扱える範囲の素数を、「PHPとPythonで巨大素数を扱う」ではPythonで巨大素数を生成した。今回は、GMP関数を利用し、PHPだけで数百桁の巨大素数の生成と、それが素数であることを判定するプログラムを作ってみる。

プログラムを実行する

ダウンロード（PHP8対応）

圧縮ファイルの内容

isPrimeGMP.php

サンプル・プログラム

GMP関数は、オープンソースの GNU Multi-Precision Library（GNU多倍長精度演算ライブラリ）を利用し、任意長の整数の演算をするための関数群である。ただし、PHPの整数型の範囲が限られているので、巨大整数を扱うときは、引数を文字列型（実体は数字）に指定しておく。

 227: /**
 228:  * 素数を発生する
 229:  * @param   int $maxdigit 最大桁数
 230:  * @return  string 素数／NULL：取得失敗
 231: */
 232: function getPrime($maxdigit) {
 233:     $digit = mt_rand(1, $maxdigit);                 //ランダムな桁数
 234: 
 235:     $min = (string)gmp_pow(10, $digit - 1);         //乱数の最小値
 236:     $max = (string)gmp_sub(gmp_pow(10, $digit), 1); //乱数の最大値
 237:     $rnd = (string)gmp_random_range($min, $max);    //乱数を求める
 238: 
 239:     $prime = (string)gmp_nextprime($rnd);           //$rndの次の素数を求める
 240: 
 241:     return $prime;
 242: }

ユーザー関数 isPrimeGMP は、引数を10進数の最大桁数とする巨大素数を発生する。演算の大部分は GMP関数を利用する。

まず、通常の整数関数  mt_rand  を使って、素数の桁数を変数 $digit に格納する。
次に、GMP関数の  gmp_pow  を利用し、乱数を求めるための最小値と最大値を求める。これを乱数発生関数  mp_random_range  に渡し、素数を求める基点となる整数を求める。

GMP関数には巨大素数を求めるための関数  gmp_nextprime が用意されている。これを利用して巨大素数を生成し、戻り値とする。

 352: //素数判定
 353: $res = FALSE;
 354: if ($errmsg == '') {
 355:     $res = gmp_prob_prime($num);
 356: }

GMP関数には、素数かどうかを判定するミラー・ラビン法関数 gmp_prob_prime が用意されている。これを使って素数かどうかを判定する。

• GMP関数：PHPマニュアル
• PHPで素数かどうか判定：ぱふぅ家のホームページ
• PHPとPythonで巨大素数を扱う：ぱふぅ家のホームページ