安全素数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

安全素数(あんぜんそすう、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, …(オンライン整数列大辞典の数列 A005385

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

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

概要[編集]

安全素数という名前は暗号理論に由来する。RSA暗号のように、安全性の根拠が素因数分解の困難に依存している方式においては、素因数分解されにくい整数 N を用いることが重要である。素因数分解アルゴリズムの一つであるポラード英語版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]

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

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

脚注[編集]

  1. ^ Prime Pages, The Top Twenty: Sophie Germain (p)
  2. ^ Cunningham Chain records