安全素数（あんぜんそすう、safe prime）は、"p" と 2"p" + 1 がともに素数である場合における 2"p" + 1 である。このとき、"p" のほうはソフィー・ジェルマン素数と呼ばれる。例えば11と 2 × 11 + 1 = 23はともに素数であるので 11 はソフィー・ジェルマン素数、23は安全素数である。安全素数が無数に存在するかどうかは分かっていない。最も小さいものは5である。安全素数を小さい順に列記するととなる。簡単に確かめられることであるが、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/"q"Z) はこの性質を持つ。2010年7月現在、知られている最も大きな安全素数は、183027 × 2 − 1 である。これは、知られている最も大きなソフィー・ジェルマン素数 183027 × 2 − 1 に対するものであって、2010年3月22日に Tom Wu が発見したものである。フェルマー素数に対するや、メルセンヌ素数に対するのような有効な素数判定法は、安全素数に対しては知られていないが、"p" が素数であることが既知ならば、2"p" + 1 の素数判定にはが有効である。また、大きな安全素数を見付けるには、 (LLR) を用いて "k" × 2 − 1 の形のものを探すのが有効である。"p" および "q" = 2"p" + 1 のみならず、2"q" + 1 がまた素数になることもある。このような素数の列を第一種と呼ぶ。一般に、"q" = 2 "q" + 1 で定義される自然数列があって、"n" = 1, …, "k" の全てで "q" が素数である場合、"q

出典:wikipedia