安全素数
From Wikipedia, the free encyclopedia
安全素数（あんぜんそすう、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 のいずれかである。
ソフィー・ジェルマン素数かつ安全素数である素数は
安全素数という名前は暗号理論に由来する。RSA暗号のように、安全性の根拠が素因数分解の困難に依存している方式においては、素因数分解されにくい整数 N を用いることが重要である。素因数分解アルゴリズムの一つであるポラードの p - 1 法は、p - 1 を割り切る素数が皆小さいという性質を持つ素因数 p を求めるために有効である。よって、この攻撃に耐えるためには、N の素因数 p として、p - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために「安全」と呼ばれる。
また、Diffie-Hellman鍵共有のように、安全性の根拠が離散対数を計算することの困難性に依存している方式においては、部分群に大きな素数位数を持つ乗法群を用いる必要がある。安全素数 q を法とする乗法群 (Z/qZ)× はこの性質を持つ。