|
|
| 1行目: |
1行目: |
| − | '''安全素数'''（あんぜんそすう、safe prime）は、''p'' と 2''p'' + 1 がともに[[素数]]である場合における 2''p'' + 1 である。このとき、''p'' のほうは[[ソフィー・ジェルマン素数]]と呼ばれる。例えば[[11]]と 2 × 11 + 1 = [[23]]はともに素数であるので 11 はソフィー・ジェルマン素数、23は安全素数である。安全素数が無数に存在するかどうかは分かっていない。最も小さいものは5である。
| + | {{テンプレート:20180815sk}} __NOINDEX__ |
| − | | |
| − | 安全素数を小さい順に列記すると
| |
| − | :[[5]], [[7]], [[11]], [[23]], [[47]], [[59]], [[83]], [[107]], [[167]], [[179]], [[227]], [[263]], [[347]], [[359]], [[383]], [[467]], [[479]], …（{{OEIS|A05385}}）
| |
| − | となる。簡単に確かめられることであるが、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,…（{{OEIS|A59455}}）
| |
| − | | |
| − | == 概要 ==
| |
| − | 安全素数という名前は[[暗号理論]]に由来する。[[RSA暗号]]のように、安全性の根拠が[[素因数分解]]の困難に依存している方式においては、素因数分解されにくい整数 ''N'' を用いることが重要である。素因数分解アルゴリズムの一つである{{仮リンク|ジョン・ポラード (数学者)|en|John Pollard (mathematician)|label=ポラード}}の ''p'' - 1 法は、''p'' - 1 を割り切る素数が皆小さいという性質を持つ素因数 ''p'' を求めるために有効である。よって、この攻撃に耐えるためには、''N'' の素因数 ''p'' として、''p'' - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために「安全」と呼ばれる。
| |
| − | | |
| − | また、[[Diffie-Hellman鍵共有]]のように、安全性の根拠が[[離散対数]]を計算することの困難性に依存している方式においては、部分群に大きな素数位数を持つ乗法[[群 (数学)|群]]を用いる必要がある。安全素数 ''q'' を法とする乗法群 ('''Z'''/''q'''''Z''')<sup>×</sup> はこの性質を持つ。
| |
| − | | |
| − | == 知られている例 ==
| |
| − | 2010年7月現在、知られている最も大きな安全素数は、183027 × 2<sup>265441</sup> − 1 である。これは、知られている最も大きなソフィー・ジェルマン素数 183027 × 2<sup>265440</sup> − 1 に対するものであって、2010年3月22日に Tom Wu が発見したものである<ref>Prime Pages, [http://primes.utm.edu/top20/page.php?id=2 The Top Twenty: Sophie Germain (p)]</ref>。
| |
| − | | |
| − | [[フェルマー素数]]に対する{{仮リンク|ペピンの判定法|en|Pépin's test}}や、[[メルセンヌ素数]]に対する{{仮リンク|リュカ-レーマーの判定法|en|Lucas–Lehmer primality test}}のような有効な素数判定法は、安全素数に対しては知られていないが、''p'' が素数であることが既知ならば、2''p'' + 1 の素数判定には{{仮リンク|ポクリントンの判定法|en|Pocklington primality test}}が有効である。また、大きな安全素数を見付けるには、{{仮リンク|リュカ＝レーマー＝リーゼルの判定法|en|Lucas–Lehmer–Riesel test}} (LLR) を用いて ''k'' × 2<sup>''N''</sup> − 1 の形のものを探すのが有効である。
| |
| − | | |
| − | ''p'' および ''q'' = 2''p'' + 1 のみならず、2''q'' + 1 がまた素数になることもある。このような素数の列を第一種{{仮リンク|カニンガム鎖|en|Cunningham chain}}と呼ぶ。一般に、''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> = 2759832934171386593519 は長さ 17 の第一種カニンガム鎖を与える<ref>[http://primerecords.dk/Cunningham_Chain_records.htm Cunningham Chain records]</ref>。これは、2010年7月現在、知られている中で最も長いものである。
| |
| − | | |
| − | == 脚注 ==
| |
| − | <references />
| |
| − | | |
| − | {{素数の分類}} | |
| − | {{DEFAULTSORT:あんせんそすう}}
| |
| − | [[Category:暗号技術]]
| |
| − | [[Category:素数]]
| |
| − | [[Category:数学に関する記事]]
| |