言葉:安全素数 | TriangleSight.Net

詳細情報

  • 検索ワード
  • 安全素数

  • 最終更新者
  • 最終更新日時
  • 2018/07/20 12:58

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

"安全素数" 寄稿者15一覧

編集者を閲覧する

関連動画

関連動画を検索する

関連画像

関連画像を検索する