強いプライム

数学において、強い素数とは、ある特別な性質を持つ素数です。強い素数の定義は、暗号学と数論では異なります。

数論において、強い素数とは、その上下の最も近い素数の算術平均よりも大きい素数です（言い換えると、前の素数よりも次の素数に近い数です）。または代数的に言えば、素数の列を( p ₁、p ₂、p ₃、...) = (2、3、5、...) と書き、p _{n が}強い素数となるのは、p _n > ⁠pn _{− 1 +} pn + _1です/2たとえば、17 は 7 番目の素数です。6番目と 8 番目の素数である 13 と 19 を足すと 32 になり、その半分は 16 です。17 は 16 より大きいため、17 は強い素数です。

最初のいくつかの強い素数は

11、17、29、37、41、59、67、71、79、97、101、107、127、137、149、163、179、191、197、223、227、239、251、269、277、281、307、311、331、347、367、379、397、419、431、439、457、461、479、487、499 ( OEISの配列A051634 ) 。​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​

p  > 5となる双子素数ペア ( p、  p  + 2 )では、3 はp  − 2 を割り切れるが p − 2 は素数ではないため、 p は常に強素数です。

暗号学では、素数pが「強い」とされるのは、以下の条件が満たされた場合である。^[1]

• pは暗号化に使用できるほど十分に大きい。通常、そのためには、暗号解読者がpと他の強い素数の積を因数分解できる妥当な計算リソースに対してpが大きすぎることが必要である。
• p  − 1 には大きな素因数があります。つまり、 ある整数a ₁と大きな素数q _{1に対して、} p  =  a ₁ q ₁ + 1 となります。
• q ₁  − 1 には大きな素因数があります。つまり、 ある整数a ₂と大きな素数q _{2に対して、} q ₁  =  a ₂ q ₂ + 1 となります。
• p  + 1 には大きな素因数があります。つまり、 ある整数a ₃と大きな素数q _{3に対して、} p  =  a ₃ q ₃ − 1 となります。

素数は暗号学的意味と数論的意味の両方で強い素数となる可能性があります。例を挙げると、439351292910452432574786963588089477522344331 は、隣接する 2 つの素数の算術平均が 62 小さいため、数論的意味で強い素数です。コンピュータの助けがなければ、この数は暗号的な意味で強い素数になります。なぜなら、439351292910452432574786963588089477522344330 には大きな素因数 1747822896920092227343 があり (そして、その 1 小さい数には大きな素因数 1683837087591611009 があり)、439351292910452432574786963588089477522344332 には大きな素因数 864608136454559457049 があり (そして、その 1 小さい数には大きな素因数 105646155480762397 がある) からです。試し割りよりも高度なアルゴリズムを使用しても、これらの数を手作業で因数分解することは困難です。最新のコンピュータ代数システムでは、これらの数をほぼ瞬時に因数分解できます。暗号的に強力な素数は、この例よりもはるかに大きくなければなりません。

RSA暗号システムの鍵生成プロセスでは、係数n は2 つの強い素数の積として選択する必要があると考える人もいます。これにより、 Pollard のp  − 1 アルゴリズムを使用したn  =  pqの因数分解が計算上不可能になります。このため、ANSI X9.31 標準では、デジタル署名用の RSA 鍵の生成に強い素数を使用することが義務付けられています。ただし、強い素数は、 Lenstra 楕円曲線因数分解や数体ふるいアルゴリズムなどの新しいアルゴリズムを使用した係数因数分解から保護しません。強い素数を生成するための追加コストを考慮すると、RSA Security は現在、鍵生成で強い素数を使用することを推奨していません。同様の (より技術的な) 議論は、Rivest と Silverman によっても行われています。^[1]

1978 年に Stephen Pohlig とMartin Hellmanは、 p − 1のすべての因数がlog ^c p 未満である場合、 p を法とする離散対数を解く問題はPに存在することを示した。したがって、 DSAなどの離散対数に基づく暗号システムでは、 p  − 1 に少なくとも 1 つの大きな素因数がある ことが求められる。

計算上大きな安全な素数は、暗号的に強力な素数である可能性が高いです。

擬素数が強擬素数であるかどうかを判断する基準は、隣接する擬素数の算術平均との不等性ではなく、基数の累乗との合同性によって決まることに注意してください。

素数がその近傍の素数の平均と等しい場合、バランス素数と呼ばれます。バランス素数より小さい場合、弱い素数と呼ばれます（弱素数と混同しないでください）。

• 暗号化と標準に関するガイド
• 3.1.4 強い素数とは何か、そしてそれは RSA システムに必要か? - RSA ラボによる強い素数と弱い素数の説明