「安全素数」の版間の差分
削除された内容 追加された内容
TAKASUGI Shinji (会話 | 投稿記録) 修正 |
en:Safe prime を参考に加筆 |
||
1行目:
'''安全素数'''（あんぜんそすう、safe prime）とは
安全素数を
:[[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]], [[7]], [[11]], [[23]], [[47]], [[59]], [[83]], [[107]], [[167]], [[179]], [[227]], [[263]], [[347]], [[359]], [[383]], [[467]], [[479]], [[503]], [[563]], [[587]], [[719]], [[839]], [[863]], [[887]], [[983]], [[1019]], [[1187]], [[1283]], [[1307]], [[1319]], [[1367]], [[1439]], [[1487]], [[1523]], [[1619]], [[1823]], [[1907]]…({{OEIS|id=A005385}}）
安全素数という名前は[[暗号理論]]に由来する。[[RSA暗号]]のように、安全性の根拠が[[素因数分解]]の困難に依存している方式においては、素因数分解されにくい整数 ''N'' を用いることが重要である。素因数分解アルゴリズムの一つであるポラードの ''p'' - 1 法は、''p'' - 1 を割り切る素数が皆小さいという性質を持つ素因数 ''p'' を求めるために有効である。よって、この攻撃に耐えるためには、''N'' の素因数 ''p'' として、''p'' - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために「安全」と呼ばれる。
また、[[Diffie-Hellman鍵共有]]のように、安全性の根拠が[[離散対数]]を計算することの困難に依存している方式においては、部分群に大きな素数位数を持つ乗法[[群 (数学)|群]]を用いる必要がある。安全素数 ''q'' を法とする乗法群 ('''Z'''/''q'''''Z''')<sup>×</sup> はこの性質を持つ。
== 知られている例 ==
2008年3月現在、知られている最も大きな安全素数は、48047305725 × 2<sup>172404</sup> − 1 である。これは、知られている最も大きなソフィ・ジェルマン素数 48047305725 × 2<sup>172403</sup> − 1 に対するものであって、2007年1月25日に David Underbakke が発見したものである<ref>[http://primes.utm.edu/primes/page.php?id=79261 The List of Largest Known Primes Home Page 内のページ]</ref>。
[[フェルマー素数]]に対する[[ペピンの判定法]]や、[[メルセンヌ素数]]に対する[[リュカ-レーマーの判定法]]のように特別に有効な素数判定法は、安全素数に対しては知られていないが、''p'' が素数であることが既知ならば、2''p'' + 1 の素数判定には Pocklington の判定法が有効である。
''p'' および ''q'' = 2''p'' + 1 のみならず、2''q'' + 1 がまた素数になることもある。このような素数の列を第一種[[カニンガム鎖]] ([[:en:Cunningham chain|en]]) と呼ぶ。一般に、''q''<sub>''n''+1</sub> = 2 ''q''<sub>''n''</sub> + 1 で定義される自然数列があって、''n'' = 1, …, ''k'' の全てで ''q''<sub>''n''</sub> が素数である場合、''q''<sub>1</sub>, …, ''q''<sub>''k''</sub> を長さ ''k'' の第一種カニンガム鎖という。このとき、''q''<sub>2</sub>, …, ''q''<sub>''k''</sub> は全て安全素数である。例えば、''q''<sub>1</sub> = 810433818265726529159 は長さ 16 の第一種カニンガム鎖を与える<ref>[http://hjem.get2net.dk/jka/math/Cunningham_Chain_records.htm Cunningham Chain records]</ref>。これは、2008年3月現在、知られている中で最も長いものである。
== 脚注 ==
<references/>
{{DEFAULTSORT:あんせんそすう}}
[[Category:暗号技術]]
[[Category:数論]]
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[en:Safe prime]]
[[fr:Nombre premier sûr]]
[[zh:安全素数]]
| |||