博士

ロボ子、Sophie Germain素数プロジェクトって知ってるか？

ロボ子

聞いたことはありますが、詳しくは知りません。どんなプロジェクトなんですか？

博士

Sophie Germain素数を集めて分析して配布するプロジェクトなのじゃ！ Sophie Germain素数っていうのは、pが素数で、かつ2p+1も素数である数のことだぞ。

ロボ子

なるほど。Safe素数やBlum素数も扱っているんですね。

博士

そう！Safe素数はpが素数で(p-1)/2も素数であるもの、Blum素数はp = 3 mod 4となる素数のことじゃ。

ロボ子

これらの素数は、公開鍵暗号で広く使われているんですね。Diffie-Hellman鍵交換とかSGCM、BBSなどで。

博士

その通り！AKS素数判定法でも使われるぞ。ところでロボ子、Sophie Germain素数は無限に存在すると思う？

ロボ子

無限に存在すると予想されていますが、まだ証明されていないんですよね。

博士

そうなんじゃ。V. Shoupによると、n以下のSophie Germain素数の数は約2Cn/ln(n)^2 ≈ 1.32032n/ln(n)^2と推定されるらしいぞ。Cは双子素数定数じゃ。

ロボ子

へー、面白いですね。このプロジェクトはKamila Szewczykさんがメンテナンスしているんですね。

博士

そうじゃ。BBS乱数生成器とかBlum-Goldwasser暗号の研究を促進するために作られたらしいぞ。

ロボ子

BBS生成器のセキュリティは、QRPと因数分解の困難さに結びついているんですね。A. SidorenkoさんとB. Schoenmakersさんの研究によると。

博士

ふむふむ。セキュリティレベルのために、法n=6800ビットが安全であると以前に理解されていたn=768ビットよりもはるかに高いことが示唆されているのは興味深いな。

ロボ子

APIも提供されているんですね。`/sophie-germain/count`で素数の数を取得したり、`/sophie-germain/submit`で素数を送信したり、`/sophie-germain/get`でデータベースをクエリしたり。

博士

そうじゃ！でも、APIの不正使用はIPアドレスの永久BANにつながるから気をつけろぞ！

ロボ子

わかりました、博士。ところで、このプロジェクトで一番重要な素数は何ですか？

博士

それはもちろん、素直な数、じゃなくて、Sophie Germain素数じゃ！