安全素数

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

概要

安全素数という名前は暗号理論に由来する。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 が発見したものである^[1]。

フェルマー素数に対するペピンの判定法（英語版）や、メルセンヌ素数に対するリュカ-レーマーの判定法のような有効な素数判定法は、安全素数に対しては知られていないが、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 の第一種カニンガム鎖を与える^[2]。これは、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 が全て素数となる。

脚注

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

[1] Prime Pages, The Top Twenty: Sophie Germain (p)

[2] Cunningham Chain records

[1]

[2]

表話編歴素数の分類
生成式	フェルマー ( $2 2 n 1$ ) メルセンヌ ( $2 p - 1$ ) 二重メルセンヌ ( $2 2 p -1 - 1$ ) ワグスタッフ ( $(2 p 1)/3$ ) プロス ( $k \cdot2 n 1$ ) 階乗 ( $n! \pm 1$ ) 素数階乗 ( $p n # \pm 1$ ) ユークリッド ( $p n # 1$ ) ピタゴラス ( $4 n 1$ ) ピアポント ( $2 u \cdot3 v 1$ ) Quartan（英語版） ( $x 4 y 4$ ) ソリナス（英語版） ( $2 a \pm 2 b \pm 1$ ) カレン ( $n \cdot2 n 1$ ) ウッダル ( $n \cdot2 n - 1$ ) Cuban（英語版） ( $(x 3 - y 3)/(x - y)$ ) キャロル ( $(2 n - 1) 2 - 2$ ) Kynea ( $(2 n 1) 2 - 2$ ) レイランド ( $x y y x$ ) サービト（英語版） ( $3\cdot2 n - 1$ ) ミルズ ( $[A] 3 n$ )
漸化式（英語版）	フィボナッチリュカペルニューマン–シャンクス–ウィリアムズペラン分割ベルモツキン
各種の性質	ヴィーフェリッヒ（英語版） (対（英語版）) ウォール–孫–孫（英語版）ウォルステンホルムウィルソン幸運フォーチュンラマヌジャン（英語版）ピライ正則強（英語版）スターン Supersingular (楕円曲線)（英語版） Supersingular (ムーンシャイン理論)（英語版）良いスーパーヒッグス（英語版）高度コトーティエント（英語版）
基数依存	ハッピー二面（英語版）回文エマープレピュニット ( $(10 n - 1)/9$ ) 置換可能 Circular（英語版）切り捨て可能 Strobogrammatic（英語版） Minimal（英語版）弱いフルサイクルプライム Unique（英語版） Primeval（英語版）自己スマランダチェ–ウェラン（英語版）
組	互いに素双子 ( $p, p 2$ ) Bi-twin chain ( $n - 1, n 1, 2 n - 1, 2 n 1, \dots$ ) 三つ子 ( $p, p 2$ or $p 4, p 6$ ) 四つ子 ( $p, p 2, p 6, p 8$ ) k−Tuple いとこ ( $p, p 4$ ) セクシー ( $p, p 6$ ) 陳ソフィー・ジェルマン ( $p, 2 p 1$ ) カニンガム鎖 ( $p, 2 p \pm 1, \dots$ ) 安全 ( $p, (p - 1)/2$ ) 算術数列（英語版） ( $p an; n = 0, 1, \dots$ ) 平衡 ( $p - n, p, p n$ )
桁数	タイタニック ( $103$ 桁以上) 巨大 ( $104$ 桁以上) メガ ( $106$ 桁以上)
複素数	アイゼンシュタイン素数（英語版）ガウス素数
合成数	擬素数概素数半素数楔数 Interprime（英語版）
関連する話題	確率的素数 Industrial-grade prime（英語版）違法素数素数の公式（英語版）素数の間隔『巨大な素数の一覧』
最初の50個	$2$ $3$ $5$ $7$ $11$ $13$ $17$ $19$ $23$ $29$ $31$ $37$ $41$ $43$ $47$ $53$ $59$ $61$ $67$ $71$ $73$ $79$ $83$ $89$ $97$ $101$ $103$ $107$ $109$ $113$ $127$ $131$ $137$ $139$ $149$ $151$ $157$ $163$ $167$ $173$ $179$ $181$ $191$ $193$ $197$ $199$ $211$ $223$ $227$ $229$
素数の一覧