素数 $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$。もしこの形のソフィー・ジェルマン素数が無限にあれば、一挙に無限個のメルセンヌ数がふるい落とされることになります。

暗号

安全なウェブサイトを開くとき、あなたのコンピュータとサーバーは、だれでも盗み聞きできるネットワーク越しに秘密の鍵を取り決めなければなりません。そのためにもっともよく使われる方法の一つは、1976 年にホイットフィールド・ディフィーとマーティン・ヘルマンが考案したもので、数百けたもある巨大な素数 $q$ を法とする計算をします。

その安全性は、ある問題、離散対数問題が $q$ を法としてむずかしいことにかかっています。$q-1$ が小さな因数に分解できると、この問題はやさしくなってしまいます。だから標準規格は、$p$ も素数である安全素数 $q=2p+1$ をすすめます。そうすれば $q-1=2p$ は巨大な素因数をもち、その抜け道はふさがれます。ソフィー・ジェルマンがフェルマー研究の補助に使った素数は、錠前になったのです。

練習問題：p = 3 では 2p + 1 が 2ᵖ − 1 をわり切り、p = 5 ではわり切らないことを確かめよ

$p=3$ は $\equiv3\pmod4$ です。$2p+1=7$、$2^3-1=7$ で、わり切ります。$p=5$ は $\equiv1\pmod4$ です。$2p+1=11$、$2^5-1=31$ で、11 の倍数ではありません。定理は $p\equiv3\pmod4$ のときだけ成り立ちます。$p\equiv1\pmod4$ のときは、$2p+1$ が $2^p+1$ をわり切ります。$2^5+1=33=3\cdot11$。

練習問題：41 から始まるカニンガム鎖を続けよ

$41\to83\to167\to335$。はじめの三つは素数ですが、$335=5\cdot67$ はちがいます。鎖の長さは 3 です。

出典： ソフィー・ジェルマンの伝記、MacTutor · Whitfield Diffie and Martin Hellman, “New Directions in Cryptography”（1976）· RFC 7919、有限体ディフィー・ヘルマン群。

ソフィー・ジェルマンの全トピック · ← ソフィー・ジェルマンの定理とフェルマーの最終定理 · ソフィー・ジェルマンの恒等式：素数に見えるものを因数分解する →

画像クレジット.