ソフィー・ジェルマン素数と暗号
素数 $p$ について $2p+1$ も素数になるとき、$p$ をソフィー・ジェルマン素数といいます。11 が素数なので 5 はそうです。$15=3\cdot5$ なので 7 はちがいます。列はこう始まります。
$$2,\ 3,\ 5,\ 11,\ 23,\ 29,\ 41,\ 53,\ 83,\ 89,\ 113,\ 131,\ldots$$それぞれに対応する素数 $2p+1$ は安全素数と呼ばれます。$5, 7, 11, 23, 47, 59, 83, \ldots$ ソフィー・ジェルマンはフェルマーについての定理のためにこれらを必要としました。二世紀後、それらはインターネットの接続を守っています。
いつか尽きるのか 100 未満にはソフィー・ジェルマン素数が 10 個、1000 未満には 37 個あります。だんだんまれになりますが、現れつづけます。無限にあることを証明できた人はいません。未解決問題で、$11$ と $13$ のように差が 2 の素数の組が無限にあるかを問う、双子素数予想の仲間です。
鎖 この操作をくり返せることがあります。$2$ から始めると、
$$2\to5\to11\to23\to47,$$ここまですべて素数で、$2\cdot47+1=95$ で途切れます。このような列は、20 世紀のはじめにそれを研究したイギリスの軍人で数学者のアラン・カニンガムにちなんで、カニンガム鎖と呼ばれます。89 から始まる鎖も長く、$89\to179\to359\to719\to1439\to2879$ と六つの素数が続きます。
オイラーとラグランジュの定理 メルセンヌ数 $2^p-1$ は、巨大な素数の候補としていちばん人気があります。オイラーが述べ、ラグランジュが 1775 年に証明したところによると、安全素数はこのお祭りに水をさすことがあります。
$p$ が $p\equiv3\pmod4$ をみたすソフィー・ジェルマン素数なら、$2p+1$ は $2^p-1$ をわり切る。
$p=11$ なら $2p+1=23$ で、実際 $2^{11}-1=2047=23\cdot89$。$p=23$ なら $2^{23}-1=8\,388\,607=47\cdot178\,481$。もしこの形のソフィー・ジェルマン素数が無限にあれば、一挙に無限個のメルセンヌ数がふるい落とされることになります。
