|
安全素数（あんぜんそすう、safe prime）は、''p'' と 2''p'' + 1 がともに素数である場合における 2''p'' + 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, …（） となる。簡単に確かめられることであるが、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)× はこの性質を持つ。 'Z)× はこの性質を持つ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「安全素数」の詳細全文を読む スポンサード リンク
|