「安全素数」の版間の差分

安全素数という名前は[[暗号理論]]に由来する。[[RSA暗号]]のように、安全性の根拠が[[素因数分解]]の困難に依存している方式においては、素因数分解されにくい整数 ''N'' を用いることが重要である。素因数分解アルゴリズムの一つである[[{{仮リンク|ジョン・ポラード (数学者)|en|John Pollard (mathematician)|label=ポラード]]}}の ''p'' - 1 法は、''p'' - 1 を割り切る素数が皆小さいという性質を持つ素因数 ''p'' を求めるために有効である。よって、この攻撃に耐えるためには、''N'' の素因数 ''p'' として、''p'' - 1 が大きな素因数を持つものを選ぶ必要がある。安全素数はこの性質を持つために「安全」と呼ばれる。

20082010年37月現在、知られている最も大きな安全素数は、48047305725183027 &times; 2^172404265441 − 1 である。これは、知られている最も大きなソフィー・ジェルマン素数 48047305725183027 &times; 2^172403265440 − 1 に対するものであって、20072010年13月2522日に DavidTom UnderbakkeWu が発見したものである<ref>Prime Pages, [http://primes.utm.edu/primestop20/page.php?id=792612 The ListTop ofTwenty: LargestSophie KnownGermain Primes Home Page 内のページ(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'' &times; 2^''N'' − 1 の形のものを探すのが有効である。

''p'' および ''q'' = 2''p'' + 1 のみならず、2''q'' + 1 がまた素数になることもある。このような素数の列を第一種[[{{仮リンク|カニンガム鎖]] ([[:|en:|Cunningham chain|en]]) }}と呼ぶ。一般に、''q''_''n''+1 = 2 ''q''_''n'' + 1 で定義される自然数列があって、''n'' = 1, …, ''k'' の全てで ''q''_''n'' が素数である場合、''q''₁, …, ''q''_''k'' を長さ ''k'' の第一種カニンガム鎖という。このとき、''q''₂, …, ''q''_''k'' は全て安全素数である。例えば、''q''₁ = 8104338182657265291592759832934171386593519 は長さ 1617 の第一種カニンガム鎖を与える<ref>[http://hjemusers.get2netcybercity.dk/jka~dsl522332/math/Cunningham_Chain_records.htm Cunningham Chain records]</ref>。これは、20082010年37月現在、知られている中で最も長いものである。

<references />