サンプル・プログラムの実行例
目次
サンプル・プログラムのダウンロード
| MillerRabinPrimalityTest.php | ミラー・ラビン素数判定プログラム（PHP版） |
| MillerRabinPrimalityTest.py | ミラー・ラビン素数判定プログラム（Python版） |
| isPrimeAPI.php | 素数発生・素数判定API（Python版） |
| isPrime.php | 巨大素数判定プログラム（PHP版） |
素数と暗号
素数を求める方法としては、「PHPで分数が有限小数かどうか判定する」で紹介したエラトステネスのふるいがあるが、これで巨大素数を求めるには時間がかかりすぎる。
視点を変えよう。与えられた整数が素数かどうかを判定するミラー・ラビン素数判定法がある。ランダムで発生した整数を、この判定に通すことで、エラトステネスのふるいより早く素数を得ることができる。
ただ、PHPでは符号付き32ビット整数までしか扱うことができないので、最大でも10進数で10桁の素数しか生成できない。
そこで、素数の生成と判定は、実用上、整数の桁数制限を受けないPythonを使って自前の WebAPI を作成し、PHPから呼び出すプログラムにする。
なお、PHPでもGMP関数を利用することで整数桁数の制約がなくなる。「PHPで巨大素数の生成と判定」をご覧いただきたい。
ミラー・ラビン素数判定プログラム（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: }
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: }
Wikipedia にRubyで書かれたプログラムがあるので、これを参考に、判定関数は MillerRabinPrimalityTest を作成した。
ミラー・ラビン素数判定プログラムは、このようにシンプルなプログラムであり、比較的高速に素数判定ができる。
ただ、この判定は絶対なものではなく、確率的なものである。1回の判定で
の確率で見逃す可能性がある。そこで、forループを回して判定確率を上げていく。つまり、 
のべき乗が与えられた整数の逆数になるだけの回数を繰り返す。与えられた整数がnとすれば、回数は 
とすることで見逃し確率を限りなくゼロに近づける。
また、PHPにはべき剰余関数がないので、ユーザー関数 modpow として用意した。
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);
1772年、数学者レオンハルト・オイラーが発見した10桁の素数 2,147,483,647 は、偶然にも32ビットの正の整数の最大値である。
もう1つは、これから1を減じた整数を判定する。32ビット環境では、1を加えるとオーバーフローしてしまうためだ。
ミラー・ラビン素数判定プログラム（Python版）
15: """
16: * ミラー・ラビン素数判定法
17: * @param int $n 判定する整数
18: * @return bool TRUE：素数である／FALSE：素数でない
19: """
20: def MillerRabinPrimalityTest(n):
21: if n == 2:
22: return True;
23: if n == 1 or n & 1 == 0:
24: return False
25:
26: d = (n - 1) >> 1
27: while d & 1 == 0:
28: d >>= 1
29:
30: for k in range(int(math.log(n, 4))):
31: a = random.randint(1, n - 1)
32: t = d
33: y = pow(a, t, n)
34:
35: while t != n - 1 and y != 1 and y != n - 1:
36: y = (y * y) % n
37: t = <<1
38:
39: if y != n - 1 and t & 1 == 0:
40: return False
41:
42: return True
そこで、実用上、整数の桁数制限のないPythonにミラー・ラビン素数判定プログラムを移植する。
PHPにはべき剰余関数があるので、プログラムはさらに短くなった。
45: sys.stdout.write("Content-type: text/html\n\n") #XREA用おまじない
46:
47: #エドゥアール・リュカが手計算で発見した素数（1876年）39桁
48: m127 = 170141183460469231731687303715884105727
49:
50: #ケンブリッジ大学の電子計算機EDSACで発見（1951年）79桁
51: n = 180 * m127 * m127 + 1
52:
53: #m217素数の判定
54: res = MillerRabinPrimalityTest(n)
55: if res:
56: msg = '素数である'
57: else:
58: msg = '素数でない'
59: sys.stdout.write("\n{0:d} は".format(n))
60: sys.stdout.write("{}<br />\n".format(msg))
61:
62: #m127 + 1の判定
63: n = n + 1
64: res = MillerRabinPrimalityTest(n)
65: if res:
66: msg = '素数である'
67: else:
68: msg = '素数でない'
69: sys.stdout.write("\n{0:d} は".format(n))
70: 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 | ★ | 発生させたい素数の桁数。nとトレードオフ。 |
| n | ★ | この整数が素数かどうか判定する。dとトレードオフ。 |
素数発生・素数判定API（Python版）
前述のPHPプログラム "isPrime.py" から呼び出すためにCGIで動作するほか、多言語からの呼び出しや単独動作ができるよう、コマンドラインからも動作するようにする。
起動時のオプションスイッチは、冒頭のコメントを参照いただきたい。
なお、コマンドラインでオプションなしで起動するとヘルプ（UTF-8）が表示されるようになっている。
上から順に
- 300桁の素数を生成し標準出力へ
- 300桁の素数を生成しJSON形式で標準出力へ
- 13が素数かどうか判定し結果を標準出力へ
- 13が素数かどうか判定し結果をJSON形式で標準出力へ
isPrimeAPI：初期値
43: # 判定可能な整数の最大桁数
44: MAX_DIGITS = 500
45:
46: # 素数発生時の乱数繰返しの最大回数
47: MAX_COUNT = 10000
48:
49: # 呼び出し元ドメイン：これ以外のドメインからの呼び出しはエラーを返す
50: #DOMAIN = "pahoo.org"
51: DOMAIN = None #ドメインチェックが不要なときなNoneにする
52:
53: # デフォルト整数
後述するが、素数発生のため繰り返し乱数発生を行う。無限ループに陥るのを回避するため、繰返しの最大回数を MAX_COUNT に設定する。
次に、CGIで呼び出す場合、このAPIを勝手に使われることを回避するため、呼び出し元のドメインを制約する。ドメイン名は DOMAIN に設定する。なお、この値を None にするとドメイン判定は行わない。
isPrimeAPI：CGI呼び出し判定
83: """
84: * CGI呼び出しされたかどうか
85: * @param なし
86: * @return book True：CGI呼び出し／False：それ以外（コマンドライン等）
87: """
88: def isCGI():
89: res = False
90: if 'SERVER_PROTOCOL' in os.environ:
91: m = re.match(r'HTTP', os.environ['SERVER_PROTOCOL'], re.IGNORECASE)
92: res = True if m else False
93: return res
isPrimeAPI：呼び出し元ドメインをチェック
95: """
96: * 呼び出し元ドメインをチェックする
97: * @param string domain ドメイン名
98: * @return bool TRUE：OK／FALSE：NG
99: """
100: def checkDomain(domain):
101: if (isCGI() == False): return True # CGI呼び出しでなければ常にTrue
102: if (domain == None): return True # domein指定が無ければ常にTrue
103: try:
104: ip = socket.gethostbyname(domain)
105: except:
106: return False
107: if (ip == os.getenv('REMOTE_ADDR')):
108: res = True
109: else:
110: res = False
111: return res
isPrimeAPI：整数のバリデーション
140: """
141: * 整数のバリデーション
142: * @param int num 整数
143: * @param int min 最小値
144: * @param int max 最大値
145: * @return string バリデート後の整数／None：不正な値
146: """
147: def validInteger(num, min, max):
148: s = str(num)
149: s = s.strip() #先頭・末尾の空白を削除
150: s = re.sub(r'[ \-\.\,\t\n]+', '', s) #不要な記号を削除
151: d = re.match(r'^[0-9]+$', s) #整数かどうかのチェック
152: if (d == None):
153: res = None
154: else:
155: res = int(s)
156: if ((res <min) or (res > max)): #範囲チェック
157: res = None
158: return res
WebAPIでは、かならずしも正しい値が渡されるとは限らないので、こうしたバリデーションが必須である。
isPrimeAPI：素数の発生
190: """
191: * 素数の発生
192: * @param int d 桁数
193: * @return int 素数／None：素数発生に失敗
194: """
195: def getPrime(d):
196: d = int(d)
197: for i in range(MAX_COUNT):
198: #乱数を発生させ
199: n = random.randint(pow(10, d - 1), pow(10, d) - 1)
200: #素数判定で素数が現れるまで繰り返す
201: res = MillerRabinPrimalityTest(n)
202: if (res):
203: break
204: #素数発生に失敗
205: if (res == False):
206: n = None
207:
208: return n
指定桁数の乱数を発生させ、これが素数であるかどうかを MillerRabinPrimalityTest でチェックすることで乱数を求めるユーザー関数が getPrime である。
乱数発生の繰り返しが無限ループに陥らないよう、冒頭で紹介した初期値 MAX_COUNT で制限してる。
isPrimeAPI：メイン・プログラム
211: results = dict()
212: d = 0
213: if (isCGI() == True):
214: sys.stdout.write("Content-type: text/html\n\n")
215:
216: #呼び出し元ドメインのチェック
217: res = checkDomain(DOMAIN)
218: if (res):
219: n = getParam('n', False, DEF_PRIME)
220: #素数発生
221: if (n == None):
222: d = getParam('d', False, int(MAX_DIGITS / 2))
223: if (d == None):
224: results['error'] = '桁数指定がありません．'
225: else:
226: #バリデート
227: d = validInteger(d, 1, MAX_DIGITS)
228: if (d == None):
229: results['error'] = '桁数が大きすぎます．' + str(MAX_DIGITS) + '桁以下にしてください．'
230: else:
231: n = getPrime(d)
232: if (d == None):
233: results['error'] = '素数発生に失敗しました．'
234: else:
235: results['num'] = n
236: results['str'] = str(n)
237: #素数判定
238: else:
239: #バリデート
240: n = validInteger(n, 1, pow(10, MAX_DIGITS) - 1)
241: if (n == None):
242: results['error'] = '整数が大きすぎます．' + str(MAX_DIGITS) + '桁以下にしてください．'
243: else:
244: n = int(n)
245: #素数判定
246: res = MillerRabinPrimalityTest(n)
247: results['num'] = n
248: results['str'] = str(n)
249: if res:
250: results['prime'] = 1
251: else:
252: results['prime'] = 0
253: else:
254: results['error'] = 'このサイトからのアクセスは受け付けられません．'
255:
256: # 出力形式
257: f = getParam('f', False, '1')
258: if (f == None):
259: f = '1' if (isCGI() == True) else '0'
260:
261: # ヘルプ出力
262: if ((n == None) and (d == None) and (isCGI() == False)):
263: print("{}".format(getHelp()))
264: # 単純出力
265: elif (f == '0'):
266: if ('error' in results):
267: print("{}".format(results['error']))
268: elif (d != 0):
269: print("{0:d}".format(results['num']))
270: else:
271: print("{0:d}".format(results['prime']))
272: # JSON形式
273: else:
274: print("{}".format(json.dumps(results, indent=4)))
いずれの場合も、結果は辞書 results に代入する。呼び出す側のPHPが多桁整数を文字列としてしか扱うことができないので、整数型と同じ内容を文字列型として返すようにした。
結果出力は、json.dumps を利用し、JSON形式の応答とする。
素数判定プログラム（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 はデフォルト整数。
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: }
ただし、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: }
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: }
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;
参考情報
Pythonだとsympyにその機能があったりする。https://t.co/oqwbBjDZWJ https://t.co/EEMxqeHZZY
— Sim (@Sim0000) October 14, 2018
参考書籍
|
現代暗号入門 いかにして秘密は守られるのか | ||
| 著者 | 神永 正博 | ||
| 出版社 | 講談社 | ||
| サイズ | 新書 |
|
|
| 発売日 | 2017年10月18日頃 | ||
| 価格 | 1,078円（税込） | ||
| ISBN | 9784065020357 | ||
| 現代の暗号技術には、純粋数学者が追究した緻密で膨大な研究成果が惜しみなく投入されている。開発者と攻撃者の熾烈な争いを追いながら、実際に使われている暗号技術を解説する。現代的な暗号の基本要素である「共通鍵暗号」「ハッシュ関数」「公開鍵暗号」にくわえ、類書ではほとんど解説のなかった、ハードウェアの面からの暗号解読についても紹介する。 | |||
|
素数はなぜ人を惹きつけるのか | ||
| 著者 | 竹内薫 | ||
| 出版社 | 朝日新聞出版 | ||
| サイズ | 新書 |
|
|
| 発売日 | 2015年02月13日頃 | ||
| 価格 | 792円（税込） | ||
| ISBN | 9784022736031 | ||
| 素数はミステリアスな数である。２、３、５、７と現れたかと思えば次は１１。出没が気まぐれなのだ。人類はこの数の規則性を明らかにするために途方もない研究の歴史を積み重ねてきた。本書では文系にもわかりやすく奥深い素数の世界を解説する。 | |||
参考サイト
- PHPで分数が有限小数かどうか判定する：ぱふぅ家のホームページ
- PHPで巨大素数の生成と判定：ぱふぅ家のホームページ
- Miller–Rabin(ミラーラビン)素数判定法について理解したい：Qiita
- ミラー・ラビン素数判定法：Wikipedia
- Cで私も素数を数えてみた：404 Blog Not Found
- Python Miller-Rabin テスト作成中：Fomalhaut of Piscis Australis
- NHKスペシャル: 『素数の魔力に囚われた人々』：杜撰な研究者の日記
そこで今回は、PHPとPythonを活用し、300桁を超える素数の生成や判定を行うプログラムを作ってみることにする。
（2022年2月11日）PHP8対応，リファラ・チェック改良