PHPとPythonで巨大素数を扱う

(1/1)
デジタル暗号の世界では巨大素数が欠かせない。一方、コンピュータの計算力の向上により、複雑な暗号が解読されてしまう。暗号を作る方は、キーとなる素数をどんどん巨大化している。
そこで今回は、PHPとPythonを活用し、300桁を超える素数の生成や判定を行うプログラムを作ってみることにする。

（2024年7月20日）Pythonプログラムのソース表示を変更，docstringをGoogleスタイルに変更

download プログラムを実行する

サンプル・プログラムの実行例

PHPとPythonで巨大素数を扱う

目次

  1. プログラムを実行する
  2. サンプル・プログラムの実行例
  3. 素数と暗号
  4. サンプル・プログラムのダウンロード
  5. ミラー・ラビン素数判定プログラム（PHP版）
  6. ミラー・ラビン素数判定プログラム（Python版）
  7. プログラムの方針
  8. 素数発生・素数判定API
  9. 素数発生・素数判定API（Python版）
  10. 素数判定プログラム（PHP版）
  11. 参考サイト

サンプル・プログラムのダウンロード

download ダウンロード（PHP8対応）

圧縮ファイルの内容
MillerRabinPrimalityTest.phpミラー・ラビン素数判定プログラム（PHP版）
MillerRabinPrimalityTest.pyミラー・ラビン素数判定プログラム（Python版）
isPrimeAPI.php素数発生・素数判定API（Python版）
isPrime.php巨大素数判定プログラム（PHP版）

素数と暗号

たとえば RSA暗号のモジュラスに用いられる素数は330ビット長（10進数で100桁）だったが、1991年に解読されてしまった。2009年には768ビット長（同232桁）が解読されている。このままだと、そろそろ1024ビット長（同308桁）が解読されるだろう。

素数を求める方法としては、「PHPで分数が有限小数かどうか判定する」で紹介したエラトステネスのふるいがあるが、これで巨大素数を求めるには時間がかかりすぎる。
視点を変えよう。与えられた整数が素数かどうかを判定するミラー・ラビン素数判定法がある。ランダムで発生した整数を、この判定に通すことで、エラトステネスのふるいより早く素数を得ることができる。

ただ、PHPでは符号付き32ビット整数までしか扱うことができないので、最大でも10進数で10桁の素数しか生成できない。
そこで、素数の生成と判定は、実用上、整数の桁数制限を受けないPythonを使って自前の WebAPI を作成し、PHPから呼び出すプログラムにする。
なお、PHPでもGMP関数を利用することで整数桁数の制約がなくなる。「PHPで巨大素数の生成と判定」をご覧いただきたい。

ミラー・ラビン素数判定プログラム（PHP版）

MillerRabinPrimalityTest.php

  11: /**
  12:  * べき剰余
  13:  * @param   number $base 基数
  14:  * @param   number $exp  指数
  15:  * @param   number $mod  除数
  16:  * @return  number べき剰余
  17: */
  18: function modpow($base, $exp, $mod) {
  19:     $res = 1;
  20:     while ($exp > 0) {
  21:         if (($exp & 1) == 1)    $res = ($res * $base) % $mod;
  22:         $base = ($base * $base) % $mod;
  23:         $exp >>= 1;
  24:     }
  25:     return $res;
  26: }

MillerRabinPrimalityTest.php

  28: /**
  29:  * ミラー・ラビン素数判定法
  30:  * @param   int $n 判定する整数
  31:  * @return  bool TRUE：素数である／FALSE：素数でない
  32: */
  33: function MillerRabinPrimalityTest($n) {
  34:     if ($n == 2)    return TRUE;
  35:     if (($n == 1) || (($n & 1) == 0))   return FALSE;
  36: 
  37:     $d = ($n - 1) >> 1;
  38:     while (($d & 1) == 0) {
  39:         $d >>= 1;
  40:     }
  41:     for ($k = 0; $k <= (int)log($n, 4); $k++) {
  42:         $a = rand(1, $n - 1);
  43:         $t = $d;
  44:         $y = modpow($a, $t, $n);
  45:         while (($t != $n - 1) && ($y != 1) && ($y != $n - 1)) {
  46:             $y = ($y * $y) % $n;
  47:             $t <<= 1;
  48:         }
  49:         if (($y != $n - 1) && (($t & 1) == 0))  return FALSE;
  50:     }
  51:     return TRUE;
  52: }

まず、PHPを使ってミラー・ラビン素数判定プログラムを作る。
Wikipedia にRubyで書かれたプログラムがあるので、これを参考に、判定関数は MillerRabinPrimalityTest を作成した。
ミラー・ラビン素数判定プログラムは、このようにシンプルなプログラムであり、比較的高速に素数判定ができる。

ただ、この判定は絶対なものではなく、確率的なものである。1回の判定で \( \displaystyle\frac{1}{4} \) の確率で見逃す可能性がある。そこで、forループを回して判定確率を上げていく。つまり、\( \displaystyle\frac{1}{4} \) のべき乗が与えられた整数の逆数になるだけの回数を繰り返す。与えられた整数がnとすれば、回数は \( \displaystyle\log_4(n) \) とすることで見逃し確率を限りなくゼロに近づける。

また、PHPにはべき剰余関数がないので、ユーザー関数 modpow として用意した。

MillerRabinPrimalityTest.php

  55: //レオンハルト・オイラーが発見した素数（1732年）10桁
  56: //偶然にも32ビット整数の最大値
  57: $n = 2147483647;
  58: 
  59: //m217素数の判定
  60: $res = MillerRabinPrimalityTest($n);
  61: $msg = $res ? '素数である' : '素数でない';
  62: printf("%d は %s<br />\n", $n, $msg);

メイン・プログラムは2つの整数を素数判定する。
1772年、数学者レオンハルト・オイラーが発見した10桁の素数 2,147,483,647 は、偶然にも32ビットの正の整数の最大値である。
もう1つは、これから1を減じた整数を判定する。32ビット環境では、1を加えるとオーバーフローしてしまうためだ。

ミラー・ラビン素数判定プログラム（Python版）

MillerRabinPrimalityTest.py
def MillerRabinPrimalityTest(n):
	"""ミラー・ラビン素数判定法
	Args:
		n(int): 判定する整数
	Returns:
		bool: True 素数である / False 素数ではない
	"""
	if n == 2:
		return True;
	if n == 1 or n & 1 == 0:
		return False


	d = (n - 1) >> 1
	while d & 1 == 0:
		d >>= 1


	for k in range(int(math.log(n, 4))):
		a = random.randint(1, n - 1)
		t = d
		y = pow(a, t, n)


		while t != n - 1 and y != 1 and y != n - 1:
			y = (y * y) % n
			t <<= 1


		if y != n - 1 and t & 1 == 0:
			return False


	return True
PHPは、デフォルトでは32ビット整数までしか扱えないため、前述の10桁のオイラー素数が上限である。これでは、RSA暗号で使われている巨大素数には全く足りない。
そこで、実用上、整数の桁数制限のないPythonにミラー・ラビン素数判定プログラムを移植する。Python のべき乗関数 pow は第3引数を指定することで、べき剰余を計算することができるので、プログラムはさらに短くなった。
1951年、ケンブリッジ大学の電子計算機EDSACを使って発見した79桁の素数は、1876年にエドゥアール・リュカが手計算で発見した最大の素数（39桁）をベースにしている。
もう1つは、これに1を加えた整数を判定する。
Pythonでは桁数を意識せずに算術演算が可能で、この巨大数をほぼ一瞬で判定できることがわかるだろう。

プログラムの方針

Pythonによるミラー・ラビン素数判定プログラムに、素数を生成する機能を追加する。これを WebAPI として使えるようにする。
フロントエンド（画面入出力）はPHPで作成し、Pythonで作った WebAPI を呼び出すことにする。
PHPとPythonで巨大素数を扱う
素数発生・素数判定API
ＵＲＬ
https://www.pahoo.org/e-soul/webtech/php06/program/isPrimeAPI.py

入力パラメータ
フィールド名 要否 内　　容
d ★ 発生させたい素数の桁数。nとトレードオフ。
n ★ この整数が素数かどうか判定する。dとトレードオフ。
応答データ（json） error エラーメッセージ（正常終了時は無し） num 判定した整数／発生した素数（数値形式） str 判定した整数／発生した素数（文字列形式） prime 判定結果：1＝素数，0＝違う（引数nのときは無し）

素数発生・素数判定API（Python版）

素数発生・素数判定APIは、Pythonで動作する "isPrimeAPI.py" である。
前述のPHPプログラム "isPrime.py" から呼び出すためにCGIで動作するほか、多言語からの呼び出しや単独動作ができるよう、コマンドラインからも動作するようにする。
起動時のオプションスイッチは、冒頭のコメントを参照いただきたい。
なお、コマンドラインでオプションなしで起動するとヘルプ（UTF-8）が表示されるようになっている。
素数発生・素数判定API（Python版）
コマインドラインから呼び出して使うと、上図のようになる。
上から順に
  1. 300桁の素数を生成し標準出力へ
  2. 300桁の素数を生成しJSON形式で標準出力へ
  3. 13が素数かどうか判定し結果を標準出力へ
  4. 13が素数かどうか判定し結果をJSON形式で標準出力へ

isPrimeAPI：初期値

isPrimeAPI.py
# 判定可能な整数の最大桁数
MAX_DIGITS = 500


# 素数発生時の乱数繰返しの最大回数
MAX_COUNT = 10000


# 呼び出し元ドメイン：これ以外のドメインからの呼び出しはエラーを返す
#DOMAIN = "pahoo.org"
DOMAIN = None		#ドメインチェックが不要なときなNoneにする
ミラー・ラビン素数判定がシンプルとはいえ、桁数が多くなればなるほど計算時間がかかる。そこで、あらかじめAPIで受け付けられる最大桁数 MAX_DIGITS を設定する。この値は自由に変更できる。

後述するが、素数発生のため繰り返し乱数発生を行う。無限ループに陥るのを回避するため、繰返しの最大回数を MAX_COUNT に設定する。

次に、CGIで呼び出す場合、このAPIを勝手に使われることを回避するため、呼び出し元のドメインを制約する。ドメイン名は DOMAIN に設定する。なお、この値を None にするとドメイン判定は行わない。

isPrimeAPI：CGI呼び出し判定

isPrimeAPI.py
def isCGI():
	"""CGI呼び出しされたかどうか
	Args:
		None
	Returns:
		bool: True CGI呼び出し／False それ以外（コマンドライン等）
	"""
	res = False
	if 'SERVER_PROTOCOL' in os.environ:
		m = re.match(r'HTTP', os.environ['SERVER_PROTOCOL'], re.IGNORECASE)
		res = True if m else False
	return res
CGIから呼び出されたかどうかは、環境変数 SERVER_PROTOCOL に "HTTP" が含まれているかどうかで判定する。

isPrimeAPI：呼び出し元ドメインをチェック

isPrimeAPI.py
def checkDomain(domain):
	"""呼び出し元ドメインをチェックする
	Args:
		domain(str): ドメイン名
	Returns:
		bool: True OK / False NG
	"""
	if (isCGI() == False):	return True	# CGI呼び出しでなければ常にTrue
	if (domain == None):	return True	# domein指定が無ければ常にTrue
	try:
		ip = socket.gethostbyname(domain)
	except:
		return False
	if (ip == os.getenv('REMOTE_ADDR')):
		res = True
	else:
		res = False
	return res
呼び出し元ドメインは、ホスト名からIPアドレスを求める関数 [socket.gethostbyname] を利用し、OSの環境変数にある REMOTE_ADDR と一致することをチェックしている。

isPrimeAPI：整数のバリデーション

isPrimeAPI.py
def validInteger(num, min, max):
	s = str(num)
	"""整数のバリデーション
	Args:
		num(int): 整数
		min(int): 最小値
		max(int): 最大値
	Returns:
		str: バリデート後の整数／None：不正な値
	"""
	s = s.strip()							#先頭・末尾の空白を削除
	s = re.sub(r'[ \-\.\,\t\n]+', '', s)	#不要な記号を削除
	d = re.match(r'^[0-9]+$', s)			#整数かどうかのチェック
	if (d == None):
		res = None
	else:
		res = int(s)
		if ((res < min) or (res > max)):	#範囲チェック
			res = None
	return res
渡される値（整数）のバリデーションを行うユーザー関数 validInteger を用意した。
WebAPIでは、かならずしも正しい値が渡されるとは限らないので、こうしたバリデーションが必須である。

isPrimeAPI：素数の発生

isPrimeAPI.py
def getPrime(d):
	"""素数を発生する
	Args:
		d(int): 桁数
	Returns:
		int: 素数 / None: 素数発生に失敗
	"""
	d = int(d)
	for i in range(MAX_COUNT):
		# 乱数を発生させ
		n = random.randint(pow(10, d - 1), pow(10, d) - 1)
		# 素数判定で素数が現れるまで繰り返す
		res = MillerRabinPrimalityTest(n)
		if (res):
			break
	# 素数発生に失敗
	if (res == False):
		n = None


	return n
素数判定の方は、すでに解説したミラー・ラビン素数判定法 MillerRabinPrimalityTest を使う。

指定桁数の乱数を発生させ、これが素数であるかどうかを MillerRabinPrimalityTest でチェックすることで乱数を求めるユーザー関数が getPrime である。
乱数発生の繰り返しが無限ループに陥らないよう、冒頭で紹介した初期値 MAX_COUNT で制限してる。

isPrimeAPI：メイン・プログラム

isPrimeAPI.py
# メイン・プログラム =======================================================
results = dict()
d = 0
if (isCGI() == True):
	sys.stdout.write("Content-type: text/html\n\n")


# 呼び出し元ドメインのチェック
res = checkDomain(DOMAIN)
if (res):
	n = getParam('n', False, DEF_PRIME)
	#素数発生
	if (n == None):
		d = getParam('d', False, int(MAX_DIGITS / 2))
		if (d == None):
			results['error'] = '桁数指定がありません．'
		else:
			# バリデート
			d = validInteger(d, 1, MAX_DIGITS)
			if (d == None):
				results['error'] = '桁数が大きすぎます．' + str(MAX_DIGITS) + '桁以下にしてください．'
			else:
				n = getPrime(d)
				if (d == None):
					results['error'] = '素数発生に失敗しました．'
				else:
					results['num'] = n
					results['str'] = str(n)
	# 素数判定
	else:
		# バリデート
		n = validInteger(n, 1, pow(10, MAX_DIGITS) - 1)
		if (n == None):
			results['error'] = '整数が大きすぎます．' + str(MAX_DIGITS) + '桁以下にしてください．'
		else:
			n = int(n)
			# 素数判定
			res = MillerRabinPrimalityTest(n)
			results['num'] = n
			results['str'] = str(n)
			if res:
				results['prime'] = 1
			else:
				results['prime'] = 0
else:
	results['error'] = 'このサイトからのアクセスは受け付けられません．'


# 出力形式
f = getParam('f', False, '1')
if (f == None):
	f = '1' if (isCGI() == True) else '0'


# ヘルプ出力
if ((n == None) and (d == None) and (isCGI() == False)):
	print("{}".format(getHelp()))
# 単純出力
elif (f == '0'):
	if ('error' in results):
		print("{}".format(results['error']))
	elif (d != 0):
		print("{0:d}".format(results['num']))
	else:
		print("{0:d}".format(results['prime']))
# JSON形式
else:
	print("{}".format(json.dumps(results, indent=4)))
メイン・プログラムでは、CGI呼び出しかどうか、オプションスイッチの内容によって処理を場合分けしてゆく。

いずれの場合も、結果は辞書 results に代入する。呼び出す側のPHPが多桁整数を文字列としてしか扱うことができないので、整数型と同じ内容を文字列型として返すようにした。
結果出力は、json.dumps を利用し、JSON形式の応答とする。

素数判定プログラム（PHP版）

素数判定プログラムは、PHPで動作する "isPrime.php" である。

isPrime.php

  36: //自力で素数を発生するか否か：TRUE＝自力発生，FALSE＝DEF_PRIMEを使用
  37: define('FLAG_GENERATE', FALSE);
  38: 
  39: //素数発生・素数判定API：各自の環境に合わせること
  40: define('API_ISPRIME', 'https://www.pahoo.org/e-soul/webtech/php06/program/isPrimeAPI.py');
  41: 
  42: //判定できる整数の最大桁数
  43: define('MAX_DIGITS', 400);
  44: 
  45: //デフォルト整数
  46: //ケンブリッジ大学の電子計算機EDSACで発見した素数（1951年）79桁
  47: define('DEF_PRIME', '5,210,644,015,679,228,794,060,694,325,390,955,853,335,898,483,908,056,458,352,183,851,018,372,555,735,221');

自由に変更できる定数がいくつかある。
初期値の素数を決める FLAG_GENERATE は、TRUEにすると自力で素数を発生させ、FALSEにすると後述する DEF_PRIME を使う。
API_ISPRIME は、前述の素数発生・素数判定API "isPrimeAPI.py" のURLを設定する。各自の環境に合わせてほしい。
MAX_DIGITS は、判定できる整数の最大桁数を設定する。素数発生・素数判定API "isPrimeAPI.py" の MAX_DIGITS より小さくすること。
DEF_PRIME はデフォルト整数。

isPrime.php

 218: /**
 219:  * 整数のバリデーション
 220:  * @param   string $num  整数
 221:  * @return  string バリデート後の整数／NULL：不正な値
 222: */
 223: function validInteger($num) {
 224:     $num = trim($num);
 225:     $num = preg_replace('/[ \-\.\,\t\n]+/ui', '', $num);
 226:     if (mb_strlen($num) > MAX_DIGITS)   return NULL;
 227:     return (preg_match('/^[0-9]+$/iu', $num) > 0) ? $num : NULL;
 228: }

入力された整数をチェックするユーザー関数 validInteger を用意した。WebAPIとの二重チェックになるが、念には念を入れた。
ただし、PHPでは多桁整数を扱うことができないので、余計な記号の削除と桁数のチェックのみを行う。

isPrime.php

 230: /**
 231:  * 素数発生APIを呼び出し、素数を取得する
 232:  * @param   string $digit  桁数
 233:  * @param   string $errmsg エラーメッセージを格納／''：エラーなし
 234:  * @return  string 素数／NULL：取得失敗
 235: */
 236: function getPrime($digit, &$errmsg) {
 237:     $prime = $errmsg = '';
 238:     $url = API_ISPRIME . '?d=' . $digit;    //素数発生API
 239:     $json = file_get_contents($url);
 240:     if ($json == FALSE) {
 241:         $errmsg = 'API error';
 242:     } else {
 243:         $arr = json_decode($json);
 244:         if (isset($arr->error)) {
 245:             $errmsg = $arr->error;
 246:         } else {
 247:             $prime = $arr->str;
 248:         }
 249:     }
 250:     return $prime;
 251: }

素数を取得するユーザー関数 getPrime は、WebAPIを呼び出し素数を取得する。WebAPIの呼び出しは  file_get_contents  で行い、応答を  json_decode  でデコードする。

isPrime.php

 253: /**
 254:  * 素数判定APIを呼び出し、素数を判定する
 255:  * @param   string $num    素数
 256:  * @param   string $errmsg エラーメッセージを格納／''：エラーなし
 257:  * @return  bool TRUE：素数である／FALSE：素数でない、またはエラー
 258: */
 259: function isPrime($num, &$errmsg) {
 260:     $res = FALSE;
 261:     $errmsg = '';
 262:     $url = API_ISPRIME . '?n=' . $num;      //素数判定API
 263: 
 264:     //バリデート
 265:     $n = validInteger($num);
 266:     if ($n != NULL) {
 267:         $json = file_get_contents($url);
 268:         if ($json == FALSE) {
 269:             $errmsg = 'APIが見つかりません．';
 270:         } else {
 271:             $arr = json_decode($json);
 272:             $errmsg = '';
 273:             if (isset($arr->error)) {
 274:                 $errmsg = $arr->error;
 275:             } else {
 276:                 $res = ($arr->prime == 0) ? FALSE : TRUE;
 277:             }
 278:         }
 279:     } else {
 280:         $errmsg = '異常な整数です．';
 281:     }
 282:     return $res;
 283: }

素数を判定するユーザー関数 isPrime は、WebAPIを呼び出し素数を取得する。WebAPIの呼び出しは  file_get_contents  で行い、応答を  json_decode  でデコードする。

isPrime.php

 370: //素数取得
 371: if (FLAG_GENERATE) {
 372:     $prime = getPrime(MAX_DIGITS, $errmsg);
 373:     if ($errmsg != '')      $prime = DEF_PRIME;
 374: }
 375: //整数を取得
 376: $num = getParam('num', FALSE, $prime);
 377: 
 378: //リセット
 379: if (isButton('reset')) {
 380:     $errmsg = '';
 381:     $prime = getPrime(MAX_DIGITS, $errmsg);
 382:     $num = validInteger($prime);
 383: }
 384: 
 385: //素数判定
 386: $res = FALSE;
 387: if ($errmsg == '') {
 388:     $res = isPrime($num, $errmsg);
 389: }
 390: 
 391: //表示処理
 392: $HtmlBody = makeCommonBody($num, $res, $errmsg);
 393: echo $HtmlHeader;
 394: echo $HtmlBody;
 395: echo $HtmlFooter;

メイン・プログラムは、まず FLAG_GENERATE を参照し、素数を発生させるかどうかを決める。次に、取得した整数に対して素数判定を行う。

参考情報

参考書籍

表紙 現代暗号入門 いかにして秘密は守られるのか
著者 神永 正博
出版社 講談社
サイズ 新書
発売日 2017年10月18日頃
価格 1,078円（税込）
ISBN 9784065020357
現代の暗号技術には、純粋数学者が追究した緻密で膨大な研究成果が惜しみなく投入されている。開発者と攻撃者の熾烈な争いを追いながら、実際に使われている暗号技術を解説する。現代的な暗号の基本要素である「共通鍵暗号」「ハッシュ関数」「公開鍵暗号」にくわえ、類書ではほとんど解説のなかった、ハードウェアの面からの暗号解読についても紹介する。
 
表紙 素数はなぜ人を惹きつけるのか
著者 竹内薫
出版社 朝日新聞出版
サイズ 新書
発売日 2015年02月13日頃
価格 792円（税込）
ISBN 9784022736031
素数はミステリアスな数である。２、３、５、７と現れたかと思えば次は１１。出没が気まぐれなのだ。人類はこの数の規則性を明らかにするために途方もない研究の歴史を積み重ねてきた。本書では文系にもわかりやすく奥深い素数の世界を解説する。
 

参考サイト

（この項おわり）
前へ 目次 次へ
関連ページ bluesky
Valid HTML5 正当なCSSです!
2018年10月14日 作成／2024年10月21日 更新
Copyright by studio pahoo, (C)2018-2024
（※）本ページはリンクフリーですが、複製・転載時にはご一報ください。
★本ページへのご意見・ご質問・お便りは、こちらへお願いします。
header
ホーム  > Web技術  > PHPでクラウド連携