セーフとソフィー・ジャーメインがプライム

数論では、素数 p がソフィー・ジェルマン素数である場合、2 p + 1 も素数である。 ソフィー・ジェルマン素数に関連付けられた 数 2 p + 1 は安全素数と呼ばれる。たとえば、11 はソフィー・ジェルマン素数であり、2 × 11 + 1 = 23 はそれに関連付けられた安全素数である。ソフィー・ジェルマン素数と安全素数は、公開鍵暗号や素数判定に応用されている。ソフィー・ジェルマン素数は無限にあると推測されているが、これはまだ証明されていない。

ソフィー・ジェルマン素数は、フェルマーの最終定理の研究で使用したフランスの数学者ソフィー・ジェルマンにちなんで名付けられました。^[1]ジェルマンがフェルマーの最終定理を証明しようとした試みの 1 つは、p を8 k + 7の形の素数とし、 n = p – 1とすることだった。この場合、は解けない。しかし、ジェルマンの証明は未完成のままでした。^{[2] [3]}フェルマーの最終定理を解く試みを通して、ジェルマンは、現在ジェルマンの定理として知られる結果を導きました。それは、p が奇数の素数で、 2 p + 1 も素数である場合、p はx、y、またはzを割り切れる必要がある、というものです。それ以外の場合は、です。 p がx、y、またはz を割り切れないこの場合は、最初のケースと呼ばれます。ソフィー・ジェルマンの仕事は、当時フェルマーの最終定理に関して達成された最大の進歩でした。^[2]クンマーらによるその後の研究では、常に問題を第一のケースと第二のケースに分けた。 ${\displaystyle x^{n}+y^{n}=z^{n}}$${\textstyle x^{n}+y^{n}\neq z^{n}}$

最初のいくつかのソフィー・ジェルマン素数（1000未満のもの）は

2、3、5、11、23、29、41、53、83、89、113、131、173、179、191、233、239、251、281、293​​、359、419、431、443、491、 509、 593、641、653、659、683、719、743、761、809、911、953、... OEIS : A005384

したがって、最初のいくつかの安全な素数は

5、7、11、23、47、59、83、107、167、179、227、263、347、359、383、467、479、503、563、587、719、839、863、887、983、1019、1187、1283、1307、1319、1367、1439、1487、1523、1619、1823、1907、... OEIS : A005385

暗号化では、 1,846,389,521,368 + 11 ⁶⁰⁰のような、はるかに大きなソフィー・ジェルマン素数が必要になります。

2つの分散コンピューティングプロジェクト、PrimeGridとTwin Prime Searchには、大きなソフィー・ジェルマン素数の探索が含まれています。次の表に、知られている最大のソフィー・ジェルマン素数のいくつかを示します。^[4]

2019 年 12 月 2 日、Fabrice Boudot、Pierrick Gaudry、Aurore Guillevic、Nadia Heninger、Emmanuel Thomé、および Paul Zimmermann は、数体ふるいアルゴリズムを使用して、240 桁 (795 ビット) の素数 RSA-240 + 49204 (RSA-240 を超える最初の安全な素数) を法とする離散対数の計算を発表しました。離散対数レコードを参照してください。

フェルマー素数やメルセンヌ素数の場合のような、安全な素数に対する特別な素数判定はありません。ただし、pの素数性が証明されれば、ポックリントンの基準を使用して 2 p + 1 の素数性を証明することができます。

第一種カニンガム連鎖の最後の項を除くすべての項がソフィー・ジャーマン素数であるのと同様に、そのような連鎖の最初の項を除くすべての項は安全素数です。7 で終わる安全素数、つまり 10 n + 7 の形式は、2(10 n  + 7) + 1 = 20 n  + 15 が5 で割り切れる ので、そのような連鎖に現れるときは最後の項になります。

安全な素数の場合、-1（非剰余^[a]の場合）を除くすべての二次非剰余は原始根である。したがって、安全な素数の場合、最小の正の原始根は素数である。^[15]

7 を除いて、安全な素数qは 6 k  − 1 またはそれと同等のq ≡ 5 ( mod 6)の形式であり、 p > 3 も同様です。同様に、5 を除いて、安全な素数qは 4 k  − 1 またはそれと同等のq ≡ 3 ( mod 4)の形式であり、 ( q − 1) / 2 は必ず奇数の 自然数 に評価されるため、これは自明です。lcm (6, 4) を使用して両方の形式を組み合わせると、安全な素数q > 7は 12 k − 1 またはそれと同等のq ≡ 11 ( mod 12) の形式でもあることがわかります。

したがって、任意の安全な素数q > 7 については次のようになります。

• 3 と 12 はどちらもq を法とする平方剰余である（平方相互法則による）
  • 3も12もqの原始根ではない
  • 12進数で完全な繰り返し素数でもある安全な素数は5と7だけです。
  • q は3 ^{( q −1)/2} − 1 と 12 ^{( q −1)/2} − 1を割り切ります。これは 3 ^{( q −1)/2} ≡ 1 mod qと 12 ^{( q −1)/2} ≡ 1 mod qと同じです(オイラーの定理による)
• q -3、q -4、q -9、q -12は2次非剰余である
  • q -3、q -4、q -9、q > 11の場合はq -12は原始根である。

pが 3 より大きいソフィー・ジェルマン素数である場合、 p は2 mod 3 と合同でなければなりません。そうでなければ、1 mod 3 と合同になり、2 p  + 1 は 3 mod 3 と合同になり、素数としては不可能です。^{[16]同様の制限はより大きな素数係数にも当てはまり、ソフィー・ジェルマン素数の密度に関するハーディ・リトルウッド推定における「補正係数」2} Cの選択の基礎となっています。^[17]

ソフィー・ジェルマン素数pが3 (mod 4) と合同である場合 ( OEIS : A002515、ルーカス素数)、それに対応する安全素数 2 p  + 1 ( 8 を法として 7 と合同) はメルセンヌ数 2 ^p  − 1の約数になります。歴史的に、レオンハルト・オイラーのこの結果は、素数指数を持つメルセンヌ数が合成数になるための最初の既知の基準でした。^[18]これは、合成数であることが知られている最大のメルセンヌ数 (素数指数を持つ) を生成するために使用できます。^[19]

ソフィー・ジェルマン素数は無限に存在すると予想されているが、これは証明されていない。^[17]数論における他のいくつかの有名な予想は、この予想と双子素数予想を一般化しており、それらにはディクソン予想、シンツェルの仮説 H、ベイトマン・ホーン予想などがある。

n未満のソフィー・ジェルマン素数の推定値は^[17]である。

${\displaystyle 2C{\frac {n}{(\ln n)^{2}}}\approx 1.32032{\frac {n}{(\ln n)^{2}}}}$

どこ

${\displaystyle C=\prod _{p>2}{\frac {p(p-2)}{(p-1)^{2}}}\approx 0.660161}$

はハーディ・リトルウッドの双子素数定数である。n  = 10 ⁴の場合、この推定値は156個のソフィー・ジェルマン素数を予測し、正確な値190と比較して20%の誤差がある。n = 10 7 の場合、推定 値^{は50822を予測し、正確な値56032からまだ10%ずれている。この推定値の形式は}GHハーディとJEリトルウッドによるもので、彼らは同様の推定値を双子素数に適用した。^[20]

 すべての数が素数である数列 ( p , 2 p + 1, 2(2 p + 1) + 1, ...) は、第一種カニンガム連鎖と呼ばれる。そのような数列 の最後の項を除くすべての項はソフィー・ジェルマン素数であり、最初の項を除くすべての項は安全素数である。ソフィー・ジェルマン素数は無限に存在するという予想を拡張して、任意の長さのカニンガム連鎖が存在するという予想もある^[21]が、無限連鎖は不可能であることが知られている^{[22] 。}

素数qが強い素数であるとは、q + 1とq − 1 の両方に大きな素因数（約 500 桁）がある場合です。安全な素数q = 2 p + 1の場合、数q − 1は当然大きな素因数、つまりpを持ち、したがって安全な素数q は強い素数であるための条件の一部を満たしています。 qを素因数として数を因数分解するいくつかの方法の実行時間は、q − 1の素因数のサイズに部分的に依存します。これは、たとえばp − 1 法に当てはまります。

安全素数は、ディフィー・ヘルマン鍵交換のような離散対数ベースの技術で使用されるため、暗号化においても重要です。2 p + 1が安全素数である場合、2 p + 1を法とする整数の乗法群には、大きな素数位数の部分群があります。通常、望ましいのはこの素数位数の部分群であり、安全素数を使用する理由は、係数がpに対して可能な限り小さくなるためです。

素数p  = 2 q + 1 は、 q が素数である場合に安全素数 と呼ばれます。したがって、p  = 2 q  + 1 が安全素数であるのは、q がソフィー・ジェルマン素数である場合に限ります。したがって、安全素数を見つけることとソフィー・ジェルマン素数を見つけることは、計算の難しさにおいて同等です。安全素数の概念は、p  − 1 とp + 1 の両方が大きな素因数を持つ強い素数に強化することができます。安全で強い素数は、 RSA 暗号システム の秘密鍵の因数として有用でした。なぜなら、それらは、ポラードのp − 1 アルゴリズムなどのいくつかの因数分解アルゴリズムによってシステムが破られるのを防ぐからです。しかし、現在の因数分解技術では、安全で強い素数を使用する利点はごくわずかであるように思われます。^[23]

同様の問題は、ディフィー・ヘルマン鍵交換や、整数因数分解ではなく離散対数問題のセキュリティに依存する類似のシステムなど、他の暗号システムにも当てはまります。 ^[24]このため、これらの方法の鍵生成プロトコルは、強い素数を生成するための効率的なアルゴリズムに依存することが多く、そのアルゴリズムは、これらの素数が十分に高い密度を持っているという推測に依存しています。^[25]

ソフィー・ジェルマン・カウンターモードでは、安全な素数2 ¹²⁸  + 12451に等しい位数の有限体での演算を使用して、 2進有限体GF(2 ^{128 )を使用した}ガロア/カウンターモードの弱点に対抗することが提案されました。しかし、SGCMはGCMと同じ多くの暗号攻撃に対して脆弱であることが示されています。^[26]

AKS素数判定テスト論文の最初のバージョンでは、ソフィー・ジェルマン素数に関する予想を用いて、最悪の計算量をO(log ¹² n )からO(log ⁶ n )に下げている。その後のバージョンでは、計算時間がO(log ^7.5 n )であることが示されており、これも予想を用いることでO(​​log ⁶ n )に下げることができる。^[27]その後のAKSの変種では、いかなる予想もソフィー・ジェルマン素数の使用もなしに、 計算量がO(log ⁶ n )であることが証明されている。

特定の合同性に従う安全な素数は、モンテカルロシミュレーションで使用される疑似乱数を生成するために使用できます。

同様に、ソフィー・ジェルマン素数は疑似乱数の生成に使用できます。 1/ qの小数展開により、 q − 1 個の 疑似乱数列が生成されます。ただし、 qはソフィー・ジェルマン素数pの安全素数であり、pは 20 を法として3、9、または 11 と合同です。 ^[28]したがって、「適切な」素数qは 7、23、47、59、167、179 などです ( OEIS : A000353 ) ( p  = 3、11、23、29、83、89 などに対応) ( OEIS : A000355 )。結果は、長さq − 1 桁の列 (先頭のゼロを含む) です。したがって、たとえばq = 23 を使用すると、0、4、3、4、7、8、2、6、0、8、6、9、5、6、5、2、1、7、3、9、1、3 という疑似乱数が生成されます。これらの数字は、それぞれの値が数字ストリーム内の前の数字から導出されるため、暗号化の目的には適していないことに注意してください。^{[引用が必要]}

ソフィー・ジェルマン素数は舞台劇『証明』 ^[29]とそれに続く映画『証明^』[30]で言及されている。

• PlanetMathでの安全な素数。
• M. Abramowitz、IA Stegun編 (1972)。数学関数ハンドブック。応用数学シリーズ。第 55 巻 (第 10 刷)。国立標準局。p. 870。