サンプル・プログラムの実行例
目次
サンプル・プログラムのダウンロード
| MillerRabinPrimalityTest.php | ミラー・ラビン素数判定プログラム（PHP版） |
| MillerRabinPrimalityTest.py | ミラー・ラビン素数判定プログラム（Python版） |
| isPrimeAPI.php | 素数発生・素数判定API（Python版） |
| isPrime.php | 巨大素数判定プログラム（PHP版） |
素数と暗号
素数を求める方法としては、「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: }
Wikipedia に Ruby で書かれたプログラムがあるので、これを参考に、判定関数は MillerRabinPrimalityTest を作成した。
ミラー・ラビン素数判定プログラムは、このようにシンプルなプログラムであり、比較的高速に素数判定ができる。
ただ、この判定は絶対なものではなく、確率的なものである。1 回の判定で
の確率で見逃す可能性がある。そこで、for ループを回して判定確率を上げていく。つまり、 
のべき乗が与えられた整数の逆数になるだけの回数を繰り返す。与えられた整数が n とすれば、回数は 
とすることで見逃し確率を限りなくゼロに近づける。
また、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);
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(a, t, n)
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
そこで、実用上、整数の桁数制限のない 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))
もう 1 つは、これに 1 を加えた整数を判定する。
Python では桁数を意識せずに算術演算が可能で、この巨大数をほぼ一瞬で判定できることがわかるだろう。
プログラムの方針
フロントエンド（画面入出力）は PHP で作成し、Python で作った WebAPI を呼び出すことにする。
| ＵＲＬ |
|---|
| https://www.pahoo.org/e-soul/webtech/php06/program/isPrimeAPI.py |
| 項目名 | フィールド名 | 型 | 内 容 |
|---|---|---|---|
| 桁数 | d | number | 発生させたい素数の桁数。nとトレードオフ。 |
| 整数 | n | number | この整数が素数かどうか判定する。dとトレードオフ。 |
素数発生・素数判定API（Python版）
前述の PHP プログラム "isPrime.py" から呼び出すために CGI で動作するほか、多言語からの呼び出しや単独動作ができるよう、コマンドラインからも動作するようにする。
起動時のオプションスイッチは、冒頭のコメントを参照いただきたい。
なお、コマンドラインでオプションなしで起動するとヘルプ（UTF-8）が表示されるようになっている。
上から順に
- 300 桁の素数を生成し標準出力へ
- 300 桁の素数を生成し JSON 形式で標準出力へ
- 13 が素数かどうか判定し結果を標準出力へ
- 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: # デフォルト整数
後述するが、素数発生のため繰り返し乱数発生を行う。無限ループに陥るのを回避するため、繰返しの最大回数を 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_PROTOCOL' in os.environ:
0091: m = re.match(r'HTTP', os.environ['SERVER_PROTOCOL'], re.IGNORECASE)
0092: res = True if m else False
0093: return res
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
isPrimeAPI：整数のバリデーション
0140: """
0141: * 整数のバリデーション
0142: * @param int num 整数
0143: * @param int min 最小値
0144: * @param int max 最大値
0145: * @return string バリデート後の整数／None：不正な値
0146: """
0147: def validInteger(num, min, max):
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 < min) or (res > max)): #範囲チェック
0157: res = None
0158: return res
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 でチェックすることで乱数を求めるユーザー関数が 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', False, DEF_PRIME)
0220: #素数発生
0221: if (n == None):
0222: d = getParam('d', False, int(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 = '1' if (isCGI() == True) else '0'
0260:
0261: # ヘルプ出力
0262: if ((n == None) and (d == None) and (isCGI() == False)):
0263: print("{}".format(getHelp()))
0264: # 単純出力
0265: elif (f == '0'):
0266: if ('error' in 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(results, indent=4)))
いずれの場合も、結果は辞書 results に代入する。呼び出す側の PHP が多桁整数を文字列としてしか扱うことができないので、整数型と同じ内容を文字列型として返すようにした。
結果出力は、json.dumps を利用し、JSON 形式の応答とする。
素数判定プログラム（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: }
ただし、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: }
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: }
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;
参考情報
Pythonだとsympyにその機能があったりする。https://t.co/oqwbBjDZWJ https://t.co/EEMxqeHZZY
— Sim (@Sim0000) October 14, 2018
参考書籍
|
現代暗号入門 いかにして秘密は守られるのか | ||
| 著者 | 神永 正博 | ||
| 出版社 | 講談社 | ||
| サイズ | 新書 | ||
| 発売日 | 2017年10月18日 | 
|
|
| 価格 | 1,058円（税込） |
 | |
| ISBN | 9784065020357 | ||
| 現代の暗号技術には、純粋数学者が追究した緻密で膨大な研究成果が惜しみなく投入されている。開発者と攻撃者の熾烈な争いを追いながら、実際に使われている暗号技術を解説する。現代的な暗号の基本要素である「共通鍵暗号」「ハッシュ関数」「公開鍵暗号」にくわえ、類書ではほとんど解説のなかった、ハードウェアの面からの暗号解読についても紹介する。 | |||
|
素数はなぜ人を惹きつけるのか | ||
| 著者 | 竹内薫 | ||
| 出版社 | 朝日新聞出版 | ||
| サイズ | 新書 | ||
| 発売日 | 2015年02月13日 |
|
|
| 価格 | 777円（税込） |
| |
| ISBN | 9784022736031 | ||
| 素数はミステリアスな数である。２、３、５、７と現れたかと思えば次は１１。出没が気まぐれなのだ。人類はこの数の規則性を明らかにするために途方もない研究の歴史を積み重ねてきた。本書では文系にもわかりやすく奥深い素数の世界を解説する。 | |||
参考サイト
- Miller-Rabin による素数の確率的判定法：深川久
- ミラー・ラビン素数判定法：Wikipedia
- PHP で分数が有限小数かどうか判定する：ぱふぅ家のホームページ
- C で私も素数を数えてみた：404 Blog Not Found
- 素数生成：Commutative Weblog 2
- Python Miller-Rabin テスト作成中：Fomalhaut of Piscis Australis
- NHK スペシャル: 『素数の魔力に囚われた人々』：杜撰な研究者の日記
そこで今回は、PHP と Python を活用し、300 桁を超える素数の生成や判定を行うプログラムを作ってみることにする。