安全素数

安全素数について

安全素数（あんぜんそすう）とは、ある素数 p と、別の数 2p + 1 が共に素数である場合の 2p + 1 を指します。この p のことをソフィー・ジェルマン素数と呼びます。例えば、p が 11 の場合、2 × 11 + 1 である 23 も素数なので、この11はソフィー・ジェルマン素数であり、23は安全素数です。なお、安全素数が無限に存在するのかどうかは現時点では分かっていません。最も小さい安全素数は 5 です。

安全素数のリスト

安全素数を小さい順に挙げると、以下のようになります：
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, …
この中で、特に 5 を除く全ての安全素数は4で割った際に3が余ります。また、7を除くと安全素数は3で割ると2が余るという性質も見られ、7より大きな安全素数は12で割ると11が余ることが確認できます。これに加え、5と11を除く安全素数はその一の位が3、7、または9であることが多いです。

また、ソフィー・ジェルマン素数であり、同時に安全素数でもある素数の例として、以下が挙げられます：
5, 11, 23, 83, 179, 359, 719, 1019, 1439, 2039, 2063, 2459, 2819, 2903, 2963,…

暗号理論における重要性

安全素数という名称の由来は暗号理論にあります。特に、RSA暗号のようにその安全性が素因数分解の難しさに依存する方式では、素因数分解が難しい整数 N の選定が重要です。素因数分解アルゴリズムの中には、ポラードの p - 1 法という、p - 1 を割り切れる小さい素数を用いる方法があります。この攻撃に強い整数 p を選ぶためには、p - 1 が大きな素因数を持つ安全素数の特性が役立ちます。

また、Diffie-Hellman鍵共有のような他の暗号方式では、安全性は離散対数問題の困難性に依存します。このため、部分群の位数が高い素数で構成される乗法群を使う必要があり、安全素数 q を用いた群はこの要件を満たします。

知られている安全素数の例

2010年7月の時点で、知られている最大の安全素数は 183027 × 2265441 − 1 という数で、これは最大のソフィー・ジェルマン素数に基づいています。この数は2010年3月22日に Tom Wu によって発見されました。

安全素数に対する有効な判定法はまだ確立されていませんが、p が素数であると分かっている場合、2p + 1 の素数性を確認するためにポクリントンの判定法が有効です。大きな安全素数を探すためには、リュカ–レーマー–リーゼル・テストが有用です。

さらに、分場合によっては、2q + 1 もまた素数になることがあります。この特性を持つ数の列は第一種カニンガム鎖と呼ばれ、全ての q の値が素数のとき、その列を長さ k の第一種カニンガム鎖と定義します。例として、q1 = 2759832934171386593519 は長さ 17 の第一種カニンガム鎖を与えます。

数列における安全素数

安全素数の中には、特定の条件を満たすものも存在します。たとえば、以下の数列に従う安全素数（ダブルセーフプライム）は次の通り：
11, 23, 47, 167, 359, 719, 1439, 2039, 2879, 4079,…
また、トリプルセーフプライムやクアトロセーフプライムにも多くの例があり、それぞれの条件を満たす素数が存在します。

このように、安全素数は数学及び暗号技術において非常に重要な概念であり、今後もさらなる研究が期待されます。

もう一度検索