知られている例

ウィキペディア小見出し辞書

知られている例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/12 14:46 UTC 版)

「安全素数」の記事における「知られている例」の解説

2010年7月現在、知られている最も大きな安全素数は、183027 × 2265441 − 1 である。これは、知られている最も大きなソフィー・ジェルマン素数 183027 × 2265440 − 1 に対するものであって、2010年3月22日に Tom Wu が発見したものである。 フェルマー素数に対するペピンの判定法（英語版）や、メルセンヌ素数に対するリュカ-レーマーの判定法（英語版）のような有効な素数判定法は、安全素数に対しては知られていないが、p が素数であることが既知ならば、2p + 1 の素数判定にはポクリントンの判定法（英語版）が有効である。また、大きな安全素数を見付けるには、リュカ–レーマー–リーゼル・テスト を用いて k × 2N − 1 の形のものを探すのが有効である。 p および q = 2p + 1 のみならず、2q + 1 がまた素数になることもある。このような素数の列を第一種カニンガム鎖と呼ぶ。一般に、qn+1 = 2 qn + 1 で定義される自然数列があって、n = 1, …, k の全てで qn が素数である場合、q1, …, qk を長さ k の第一種カニンガム鎖という。このとき、q2, …, qk は全て安全素数である。例えば、q1 = 2759832934171386593519 は長さ 17 の第一種カニンガム鎖を与える。これは、2010年7月現在、知られている中で最も長いものである。