PHPとPythonで巨大素数を扱う

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

(2022年2月11日)PHP8対応,リファラ・チェック改良

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

PHPとPythonで巨大素数を扱う

目次

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

圧縮ファイルの内容
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版)

0011: /**
0012:  * べき剰余
0013:  * @param   number $base 基数
0014:  * @param   number $exp  指数
0015:  * @param   number $mod  除数
0016:  * @return  number べき剰余
0017: */
0018: function modpow($base$exp$mod) {
0019:     $res = 1;
0020:     while ($exp > 0) {
0021:         if (($exp & 1) == 1)    $res = ($res * $base) % $mod;
0022:         $base = ($base * $base) % $mod;
0023:         $exp >>= 1;
0024:     }
0025:     return $res;
0026: }

0028: /**
0029:  * ミラー・ラビン素数判定法
0030:  * @param   int $n 判定する整数
0031:  * @return  bool TRUE:素数である/FALSE:素数でない
0032: */
0033: function MillerRabinPrimalityTest($n) {
0034:     if ($n == 2)    return TRUE;
0035:     if (($n == 1) || (($n & 1) == 0))   return FALSE;
0036: 
0037:     $d = ($n - 1) >> 1;
0038:     while (($d & 1) == 0) {
0039:         $d >>= 1;
0040:     }
0041:     for ($k = 0; $k <= (int)log($n, 4); $k++) {
0042:         $a = rand(1, $n - 1);
0043:         $t = $d;
0044:         $y = modpow($a$t$n);
0045:         while (($t != $n - 1) && ($y != 1) && ($y != $n - 1)) {
0046:             $y = ($y * $y) % $n;
0047:             $t <<= 1;
0048:         }
0049:         if (($y != $n - 1) && (($t & 1) == 0))    return FALSE;
0050:     }
0051:     return TRUE;
0052: }

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

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

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

0055: //レオンハルト・オイラーが発見した素数(1732年)10桁
0056: //偶然にも32ビット整数の最大値
0057: $n = 2147483647;
0058: 
0059: //m217素数の判定
0060: $res = MillerRabinPrimalityTest($n);
0061: $msg = $res ? '素数である' : '素数でない';
0062: printf("%d は %s<br />\n", $n$msg);

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

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

0015: """
0016:  * ミラー・ラビン素数判定法
0017:  * @param   int $n 判定する整数
0018:  * @return  bool TRUE:素数である/FALSE:素数でない
0019: 
"""
0020: def MillerRabinPrimalityTest(n):
0021:     if n == 2:
0022:         return True;
0023:     if n == 1 or n & 1 == 0:
0024:         return False
0025: 
0026:     d = (n - 1) >> 1
0027:     while d & 1 == 0:
0028:         d >>= 1
0029: 
0030:     for k in range(int(math.log(n, 4))):
0031:         a = random.randint(1, n - 1)
0032:         t = d
0033:         y = pow(atn)
0034: 
0035:         while t != n - 1 and y != 1 and y != n - 1:
0036:             y = (y * y) % n
0037:             t <<= 1
0038: 
0039:         if y != n - 1 and t & 1 == 0:
0040:             return False
0041: 
0042:     return True

PHPは、デフォルトでは32ビット整数までしか扱えないため、前述の10桁のオイラー素数が上限である。これでは、RSA暗号で使われている巨大素数には全く足りない。
そこで、実用上、整数の桁数制限のないPythonにミラー・ラビン素数判定プログラムを移植する。
PHPにはべき剰余関数があるので、プログラムはさらに短くなった。

0045: sys.stdout.write("Content-type: text/html\n\n")  #XREA用おまじない
0046: 
0047: #エドゥアール・リュカが手計算で発見した素数(1876年)39桁
0048: m127 = 170141183460469231731687303715884105727
0049: 
0050: #ケンブリッジ大学の電子計算機EDSACで発見(1951年)79桁
0051: n = 180 * m127 * m127 + 1
0052: 
0053: #m217素数の判定
0054: res = MillerRabinPrimalityTest(n)
0055: if res:
0056:     msg = '素数である'
0057: else:
0058:     msg = '素数でない'
0059: sys.stdout.write("\n{0:d} は".format(n))
0060: sys.stdout.write("{}<br />\n".format(msg))
0061: 
0062: #m127 + 1の判定
0063: n = n + 1
0064: res = MillerRabinPrimalityTest(n)
0065: if res:
0066:     msg = '素数である'
0067: else:
0068:     msg = '素数でない'
0069: sys.stdout.write("\n{0:d} は".format(n))
0070: sys.stdout.write("{}<br />\n".format(msg))

1951年、ケンブリッジ大学の電子計算機EDSACを使って発見した79桁の素数は、1876年にエドゥアール・リュカが手計算で発見した最大の素数(39桁)をベースにしている。
もう1つは、これに1を加えた整数を判定する。
Pythonでは桁数を意識せずに算術演算が可能で、この巨大数をほぼ一瞬で判定できることがわかるだろう。

プログラムの方針

Pythonによるミラー・ラビン素数判定プログラムに、素数を生成する機能を追加する。これを WebAPI として使えるようにする。
フロントエンド(画面入出力)はPHPで作成し、Pythonで作った WebAPI を呼び出すことにする。
PHPとPythonで巨大素数を扱う
素数発生・素数判定API
URL
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:初期値

0043: # 判定可能な整数の最大桁数
0044: MAX_DIGITS = 500
0045: 
0046: # 素数発生時の乱数繰返しの最大回数
0047: MAX_COUNT = 10000
0048: 
0049: # 呼び出し元ドメイン:これ以外のドメインからの呼び出しはエラーを返す
0050: #DOMAIN = "pahoo.org"
0051: DOMAIN = None       #ドメインチェックが不要なときなNoneにする
0052: 
0053: # デフォルト整数

ミラー・ラビン素数判定がシンプルとはいえ、桁数が多くなればなるほど計算時間がかかる。そこで、あらかじめAPIで受け付けられる最大桁数 MAX_DIGITS を設定する。この値は自由に変更できる。

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

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

isPrimeAPI:CGI呼び出し判定

0083: """
0084:  * CGI呼び出しされたかどうか
0085:  * @param   なし
0086:  * @return  book True:CGI呼び出し/False:それ以外(コマンドライン等)
0087: 
"""
0088: def isCGI():
0089:     res = False
0090:     if 'SERVER_PROTOCOLin os.environ:
0091:         m = re.match(r'HTTP', os.environ['SERVER_PROTOCOL'], re.IGNORECASE)
0092:         res = True if m else False
0093:     return res

CGIから呼び出されたかどうかは、環境変数 SERVER_PROTOCOL に "HTTP" が含まれているかどうかで判定する。

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

0095: """
0096:  * 呼び出し元ドメインをチェックする
0097:  * @param   string domain ドメイン名
0098:  * @return  bool TRUE:OK/FALSE:NG
0099: 
"""
0100: def checkDomain(domain):
0101:     if (isCGI() == False):   return True # CGI呼び出しでなければ常にTrue
0102:     if (domain == None): return True # domein指定が無ければ常にTrue
0103:     try:
0104:         ip = socket.gethostbyname(domain)
0105:     except:
0106:         return False
0107:     if (ip == os.getenv('REMOTE_ADDR')):
0108:         res = True
0109:     else:
0110:         res = False
0111:     return res

呼び出し元ドメインは、ホスト名からIPアドレスを求める関数 [socket.gethostbyname] を利用し、OSの環境変数にある REMOTE_ADDR と一致することをチェックしている。

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

0140: """
0141:  * 整数のバリデーション
0142:  * @param   int num 整数
0143:  * @param   int min 最小値
0144:  * @param   int max 最大値
0145:  * @return  string バリデート後の整数/None:不正な値
0146: 
"""
0147: def validInteger(numminmax):
0148:     s = str(num)
0149:     s = s.strip()                            #先頭・末尾の空白を削除
0150:     s = re.sub(r'[ \-\.\,\t\n]+', '', s)   #不要な記号を削除
0151:     d = re.match(r'^[0-9]+$', s)         #整数かどうかのチェック
0152:     if (d == None):
0153:         res = None
0154:     else:
0155:         res = int(s)
0156:         if ((res < minor (res > max)): #範囲チェック
0157:             res = None
0158:     return res

渡される値(整数)のバリデーションを行うユーザー関数 validInteger を用意した。
WebAPIでは、かならずしも正しい値が渡されるとは限らないので、こうしたバリデーションが必須である。

isPrimeAPI:素数の発生

0190: """
0191:  * 素数の発生
0192:  * @param   int d 桁数
0193:  * @return  int 素数/None:素数発生に失敗
0194: 
"""
0195: def getPrime(d):
0196:     d = int(d)
0197:     for i in range(MAX_COUNT):
0198:         #乱数を発生させ
0199:         n = random.randint(pow(10, d - 1), pow(10, d) - 1)
0200:         #素数判定で素数が現れるまで繰り返す
0201:         res = MillerRabinPrimalityTest(n)
0202:         if (res):
0203:             break
0204:     #素数発生に失敗
0205:     if (res == False):
0206:         n = None
0207: 
0208:     return n

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

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

isPrimeAPI:メイン・プログラム

0211: results = dict()
0212: d = 0
0213: if (isCGI() == True):
0214:     sys.stdout.write("Content-type: text/html\n\n")
0215: 
0216: #呼び出し元ドメインのチェック
0217: res = checkDomain(DOMAIN)
0218: if (res):
0219:     n = getParam('n', FalseDEF_PRIME)
0220:     #素数発生
0221:     if (n == None):
0222:         d = getParam('d', Falseint(MAX_DIGITS / 2))
0223:         if (d == None):
0224:             results['error'] = '桁数指定がありません.'
0225:         else:
0226:             #バリデート
0227:             d = validInteger(d, 1, MAX_DIGITS)
0228:             if (d == None):
0229:                 results['error'] = '桁数が大きすぎます.' + str(MAX_DIGITS) + '桁以下にしてください.'
0230:             else:
0231:                 n = getPrime(d)
0232:                 if (d == None):
0233:                     results['error'] = '素数発生に失敗しました.'
0234:                 else:
0235:                     results['num'] = n
0236:                     results['str'] = str(n)
0237:     #素数判定
0238:     else:
0239:         #バリデート
0240:         n = validInteger(n, 1, pow(10, MAX_DIGITS) - 1)
0241:         if (n == None):
0242:             results['error'] = '整数が大きすぎます.' + str(MAX_DIGITS) + '桁以下にしてください.'
0243:         else:
0244:             n = int(n)
0245:             #素数判定
0246:             res = MillerRabinPrimalityTest(n)
0247:             results['num'] = n
0248:             results['str'] = str(n)
0249:             if res:
0250:                 results['prime'] = 1
0251:             else:
0252:                 results['prime'] = 0
0253: else:
0254:     results['error'] = 'このサイトからのアクセスは受け付けられません.'
0255: 
0256: # 出力形式
0257: f = getParam('f', False, '1')
0258: if (f == None):
0259:     f = '1if (isCGI() == Trueelse '0'
0260: 
0261: # ヘルプ出力
0262: if ((n == Noneand (d == Noneand (isCGI() == False)):
0263:     print("{}".format(getHelp()))
0264: # 単純出力
0265: elif (f == '0'):
0266:     if ('errorin results):
0267:         print("{}".format(results['error']))
0268:     elif (d != 0):
0269:         print("{0:d}".format(results['num']))
0270:     else:
0271:         print("{0:d}".format(results['prime']))
0272: # JSON形式
0273: else:
0274:     print("{}".format(json.dumps(resultsindent=4)))

メイン・プログラムでは、CGI呼び出しかどうか、オプションスイッチの内容によって処理を場合分けしてゆく。

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

素数判定プログラム(PHP版)

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

0036: //自力で素数を発生するか否か:TRUE=自力発生,FALSE=DEF_PRIMEを使用
0037: define('FLAG_GENERATE', FALSE);
0038: 
0039: //素数発生・素数判定API:各自の環境に合わせること
0040: define('API_ISPRIME', 'https://www.pahoo.org/e-soul/webtech/php06/program/isPrimeAPI.py');
0041: 
0042: //判定できる整数の最大桁数
0043: define('MAX_DIGITS', 400);
0044: 
0045: //デフォルト整数
0046: //ケンブリッジ大学の電子計算機EDSACで発見した素数(1951年)79桁
0047: 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 はデフォルト整数。

0218: /**
0219:  * 整数のバリデーション
0220:  * @param   string $num  整数
0221:  * @return  string バリデート後の整数/NULL:不正な値
0222: */
0223: function validInteger($num) {
0224:     $num = trim($num);
0225:     $num = preg_replace('/[ \-\.\,\t\n]+/ui', '', $num);
0226:     if (mb_strlen($num) > MAX_DIGITS)   return NULL;
0227:     return (preg_match('/^[0-9]+$/iu', $num) > 0) ? $num : NULL;
0228: }

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

0230: /**
0231:  * 素数発生APIを呼び出し、素数を取得する
0232:  * @param   string $digit  桁数
0233:  * @param   string $errmsg エラーメッセージを格納/'':エラーなし
0234:  * @return  string 素数/NULL:取得失敗
0235: */
0236: function getPrime($digit, &$errmsg) {
0237:     $prime = $errmsg = '';
0238:     $url = API_ISPRIME . '?d=' . $digit;  //素数発生API
0239:     $json = file_get_contents($url);
0240:     if ($json == FALSE) {
0241:         $errmsg = 'API error';
0242:     } else {
0243:         $arr = json_decode($json);
0244:         if (isset($arr->error)) {
0245:             $errmsg = $arr->error;
0246:         } else {
0247:             $prime = $arr->str;
0248:         }
0249:     }
0250:     return $prime;
0251: }

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

0253: /**
0254:  * 素数判定APIを呼び出し、素数を判定する
0255:  * @param   string $num    素数
0256:  * @param   string $errmsg エラーメッセージを格納/'':エラーなし
0257:  * @return  bool TRUE:素数である/FALSE:素数でない、またはエラー
0258: */
0259: function isPrime($num, &$errmsg) {
0260:     $res = FALSE;
0261:     $errmsg = '';
0262:     $url = API_ISPRIME . '?n=' . $num;        //素数判定API
0263: 
0264:     //バリデート
0265:     $n = validInteger($num);
0266:     if ($n != NULL) {
0267:         $json = file_get_contents($url);
0268:         if ($json == FALSE) {
0269:             $errmsg = 'APIが見つかりません.';
0270:         } else {
0271:             $arr = json_decode($json);
0272:             $errmsg = '';
0273:             if (isset($arr->error)) {
0274:                 $errmsg = $arr->error;
0275:             } else {
0276:                 $res = ($arr->prime == 0) ? FALSE : TRUE;
0277:             }
0278:         }
0279:     } else {
0280:         $errmsg = '異常な整数です.';
0281:     }
0282:     return $res;
0283: }

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

0370: //素数取得
0371: if (FLAG_GENERATE) {
0372:     $prime = getPrime(MAX_DIGITS$errmsg);
0373:     if ($errmsg != '')      $prime = DEF_PRIME;
0374: }
0375: //整数を取得
0376: $num = getParam('num', FALSE$prime);
0377: 
0378: //リセット
0379: if (isButton('reset')) {
0380:     $errmsg = '';
0381:     $prime = getPrime(MAX_DIGITS$errmsg);
0382:     $num = validInteger($prime);
0383: }
0384: 
0385: //素数判定
0386: $res = FALSE;
0387: if ($errmsg == '') {
0388:     $res = isPrime($num$errmsg);
0389: }
0390: 
0391: //表示処理
0392: $HtmlBody = makeCommonBody($num$res$errmsg);
0393: echo $HtmlHeader;
0394: echo $HtmlBody;
0395: echo $HtmlFooter;

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

参考情報

参考書籍

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

参考サイト

(この項おわり)
header