安全素数

安全素数︵あんぜんそすう、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を用いることが重要である。素因数分解アルゴリズムの一つであるポラードの p- 1 法は、p - 1 を割り切る素数が皆小さいという性質を持つ素因数 pを求めるために有効である。よって、この攻撃に耐えるためには、N の素因数 pとして、p - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために﹁安全﹂と呼ばれる。

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

知られている例

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

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

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

各種数列

●p, (p − 1) /2, (p − 3) /4 が全て素数になる安全素数︵ダブルセーフプライム︶は

11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079, 4127, 4919, 5639, 5807, 5927, 6047, 7247, 7559, 7607, 7727, 9839,…︵オンライン整数列大辞典の数列 A66179︶

例: 5807の場合は 1451→2903→5807 が全て素数となる。

●p, (p − 1) /2, (p − 3) /4, (p − 7) /8 が全て素数になる安全素数︵トリプルセーフプライム︶は

23, 47, 719, 1439, 2879, 4079, 9839, 11279, 21599, 28319, 51599, 84719, 92399, 95279, 96959, 137279, 157679, 159119,…︵オンライン整数列大辞典の数列 A157358︶

例: 21599の場合は 2699→5399→10799→21599 が全て素数となる。

●p, (p − 1) /2, (p − 3) /4, (p − 7) /8, (p − 15) /16 が全て素数になる安全素数︵クアトロセーフプライム︶は

47, 1439, 2879, 858239, 861599, 982559, 1014719, 1067999, 2029439, 2034239, 2297759,… ︵オンライン整数列大辞典の数列 A157359︶

例: 858239の場合は 53639→107279→214559→429119→858239 が全て素数となる。