PHPとPythonで巨大素数を扱う

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

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

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版)

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: }
0027: 
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);
0063: 
0064: //m217 - 1の判定
0065: $n--;
0066: $res = MillerRabinPrimalityTest($n);
0067: $msg = $res ? '素数である' : '素数でない';
0068: printf("%d は %s", $n$msg);

メイン・プログラムは 2 つの整数を素数判定する。
1732 年、数学者レオンハルト・オイラーが発見した 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

入力パラメータ(GET)
項目名 フィールド名 内  容
桁数 d number 発生させたい素数の桁数。nとトレードオフ。
整数 n number この整数が素数かどうか判定する。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" である。

0023: //自力で素数を発生するか否か:TRUE=自力発生,FALSE=DEF_PRIMEを使用
0024: define('FLAG_GENERATE', FALSE);
0025: 
0026: //素数発生・素数判定API:各自の環境に合わせること
0027: define('API_ISPRIME', 'https://www.pahoo.org/e-soul/webtech/php06/program/isPrimeAPI.py');
0028: 
0029: //判定できる整数の最大桁数
0030: define('MAX_DIGITS', 400);
0031: 
0032: //デフォルト整数
0033: //ケンブリッジ大学の電子計算機EDSACで発見した素数(1951年)79桁
0034: 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 はデフォルト整数。

0168: /**
0169:  * 整数のバリデーション
0170:  * @param string $num  整数
0171:  * @return string バリデート後の整数/NULL:不正な値
0172: */
0173: function validInteger($num) {
0174:     $num = trim($num);
0175:     $num = preg_replace('/[ \-\.\,\t\n]+/ui', '', $num);
0176:     if (mb_strlen($num) > MAX_DIGITS)   return NULL;
0177:     return (preg_match('/^[0-9]+$/iu', $num) > 0) ? $num : NULL;
0178: }

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

0180: /**
0181:  * 素数発生APIを呼び出し、素数を取得する
0182:  * @param string $digit  桁数
0183:  * @param string $errmsg エラーメッセージを格納/'':エラーなし
0184:  * @return string 素数/NULL:取得失敗
0185: */
0186: function getPrime($digit, &$errmsg) {
0187:     $prime = $errmsg = '';
0188:     $url = API_ISPRIME . '?d=' . $digit;   //素数発生API
0189:     $json = file_get_contents($url);
0190:     if ($json == FALSE) {
0191:         $errmsg = 'API error';
0192:     } else {
0193:         $arr = json_decode($json);
0194:         if (isset($arr->error)) {
0195:             $errmsg = $arr->error;
0196:         } else {
0197:             $prime = $arr->str;
0198:         }
0199:     }
0200:     return $prime;
0201: }

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

0203: /**
0204:  * 素数判定APIを呼び出し、素数を判定する
0205:  * @param string $num    素数
0206:  * @param string $errmsg エラーメッセージを格納/'':エラーなし
0207:  * @return bool TRUE:素数である/FALSE:素数でない、またはエラー
0208: */
0209: function isPrime($num, &$errmsg) {
0210:     $res = FALSE;
0211:     $errmsg = '';
0212:     $url = API_ISPRIME . '?n=' . $num;     //素数判定API
0213: 
0214:     //バリデート
0215:     $n = validInteger($num);
0216:     if ($n != NULL) {
0217:         $json = file_get_contents($url);
0218:         if ($json == FALSE) {
0219:             $errmsg = 'APIが見つかりません.';
0220:         } else {
0221:             $arr = json_decode($json);
0222:             $errmsg = '';
0223:             if (isset($arr->error)) {
0224:                 $errmsg = $arr->error;
0225:             } else {
0226:                 $res = ($arr->prime == 0) ? FALSE : TRUE;
0227:             }
0228:         }
0229:     } else {
0230:         $errmsg = '異常な整数です.';
0231:     }
0232:     return $res;
0233: }

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

0303: $errmsg = '';
0304: $prime = DEF_PRIME;
0305: 
0306: //素数取得
0307: if (FLAG_GENERATE) {
0308:     $prime = getPrime(MAX_DIGITS$errmsg);
0309:     if ($errmsg != '')      $prime = DEF_PRIME;
0310: }
0311: //整数を取得
0312: $num = getParam('num', FALSE$prime);
0313: 
0314: //リセット
0315: if (isButton('reset'))  $num = $prime;
0316: 
0317: //素数判定
0318: $res = FALSE;
0319: if ($errmsg == '') {
0320:     $res = isPrime($num$errmsg);
0321: }
0322: 
0323: // 表示処理
0324: $HtmlBody = makeCommonBody($num$res$errmsg);
0325: echo $HtmlHeader;
0326: echo $HtmlBody;
0327: echo $HtmlFooter;

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

参考情報

参考書籍

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

参考サイト

(この項おわり)
header