「安全素数」の版間の差分
削除された内容 追加された内容
m ボット: 言語間リンク 9 件をウィキデータ上の d:Q2298723 に転記 |
PrimeHunter (会話 | 投稿記録) update url to moved site |
||
17行目:
[[フェルマー素数]]に対する{{仮リンク|ペピンの判定法|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://
== 脚注 ==
| |||