安全素数

提供: miniwiki
2018/8/19/ (日) 17:35時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
移動先:案内検索

安全素数(あんぜんそすう、safe prime)は、p と 2p + 1 がともに素数である場合における 2p + 1 である。このとき、p のほうはソフィー・ジェルマン素数と呼ばれる。例えば11と 2 × 11 + 1 = 23はともに素数であるので 11 はソフィー・ジェルマン素数、23は安全素数である。安全素数が無数に存在するかどうかは分かっていない。最も小さいものは5である。

安全素数を小さい順に列記すると

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, …(オンライン整数列大辞典の数列 A05385

となる。簡単に確かめられることであるが、5 以外の安全素数は4で割ると3余る。また7以外の安全素数は3で割ると2余る。よって、7より大きな安全素数は12で割ると11余る。

5と11を除く安全素数の一の位は 3, 7, 9 のいずれかである。

ソフィー・ジェルマン素数かつ安全素数である素数は

5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963,…(オンライン整数列大辞典の数列 A59455

概要

安全素数という名前は暗号理論に由来する。RSA暗号のように、安全性の根拠が素因数分解の困難に依存している方式においては、素因数分解されにくい整数 N を用いることが重要である。素因数分解アルゴリズムの一つであるポラードEnglish版p - 1 法は、p - 1 を割り切る素数が皆小さいという性質を持つ素因数 p を求めるために有効である。よって、この攻撃に耐えるためには、N の素因数 p として、p - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために「安全」と呼ばれる。

また、Diffie-Hellman鍵共有のように、安全性の根拠が離散対数を計算することの困難性に依存している方式においては、部分群に大きな素数位数を持つ乗法を用いる必要がある。安全素数 q を法とする乗法群 (Z/qZ)× はこの性質を持つ。

知られている例

2010年7月現在、知られている最も大きな安全素数は、183027 × 2265441 − 1 である。これは、知られている最も大きなソフィー・ジェルマン素数 183027 × 2265440 − 1 に対するものであって、2010年3月22日に Tom Wu が発見したものである[1]

フェルマー素数に対するペピンの判定法English版や、メルセンヌ素数に対するリュカ-レーマーの判定法English版のような有効な素数判定法は、安全素数に対しては知られていないが、p が素数であることが既知ならば、2p + 1 の素数判定にはポクリントンの判定法English版が有効である。また、大きな安全素数を見付けるには、リュカ=レーマー=リーゼルの判定法English版 (LLR) を用いて k × 2N − 1 の形のものを探すのが有効である。

p および q = 2p + 1 のみならず、2q + 1 がまた素数になることもある。このような素数の列を第一種カニンガム鎖English版と呼ぶ。一般に、qn+1 = 2 qn + 1 で定義される自然数列があって、n = 1, …, k の全てで qn が素数である場合、q1, …, qk を長さ k の第一種カニンガム鎖という。このとき、q2, …, qk は全て安全素数である。例えば、q1 = 2759832934171386593519 は長さ 17 の第一種カニンガム鎖を与える[2]。これは、2010年7月現在、知られている中で最も長いものである。

脚注