こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz 
です。
はじめに
人名がついた「●●素数（●●は人の名前）」という素数を紹介する第１０弾です。これまでの９つのエントリは脚注にリンクを貼っておきます。123456789
最初に、このあとプログラムで本題の素数の列を求める例を示しますが、その前に事前準備として確率的素数を判定する関数を定義しておきます。
ghci> exp_mod a n = iter a (n-1) n where iter a n base | n == 1 = a | even n = (iter a (n `div` 2) base) ^ 2 `mod` base | otherwise = a * (iter a ((n-1) `div` 2) base) ^ 2 `mod` base
ghci> probably_prime n = and $ map (\a -> test n a) $ takeWhile (<n) [2,3,5,7,11,13,17,19] where test n a | gcd n a == 1 = (1 == exp_mod a n) | otherwise = False
また、素数列を利用しますのでワンライナーで素数列を定義しておきます。
ghci> p=2:3:5:5#p;m#(a:b:x)=[n|n<-[a^2..b^2-2],(mod (n+1) 6)*(mod (n-1) 6)==0,gcd n m<2]++(m*b)#(b:x)
本稿で扱うソフィー・ジェルマン素数と安全素数は、@tsujimotterさんのYouTubeでも紹介されています。わかりやすい解説動画ですので是非ご覧頂ければ幸いです。
ソフィー・ジェルマン素数と安全素数
ソフィー・ジェルマン素数のWikiPediaによると、フランスの数学者ソフィー・ジェルマンにちなんで名付けられた素数で、$2p + 1$ もまた素数であるような素数 $p$ を『ソフィー・ジェルマン素数』と呼びます。その対となる素数 $2p + 1$ の方を『安全素数（safe prime）』と呼びます。
ソフィージェルマン素数と安全素数の定義は以下のとおりです。
- ソフィー・ジェルマン素数の定義
- $ 2p + 1 $ が素数となる素数 $p$
- 安全素数の定義
- $ (p - 1) / 2 $ が素数となる素数 $p$
ソフィー・ジェルマンといえば、性別に対する偏見があったために男性の名前を名乗って数学をしていたとされます（WikiPediaを参照）が、著名で超一流の当時の数学者（物理学者）であるラグランジュ、ルジャンドル、ガウスと文通で研究をしており、後世でも賞賛されるべき業績を残した数学者です。
その業績の１つに『フェルマーの最終定理の研究』があり、フェルマーの最終定理で $p$ が $x, y, z$ のいずれも割り切れない場合（ファーストケース）に、ソフィー・ジェルマン素数のときにフェルマーの最終定理が成り立つことを示す『ソフィー・ジェルマンの定理』を発見しました。
この証明は、せきゅーんさんのブログに詳しく紹介されております。
このソフィー・ジェルマンの定理で対象となる素数が『ソフィー・ジェルマン素数』と呼ばれる由来です。
さて、Haskellプログラムでは、安全素数の列から逆算してソフィー・ジェルマン素数との組みを調べる方法として、最初の100個を出力する例を次に紹介します。
ghci> p'=[(sg,sf)| sf<-filter (\n -> probably_prime ((n-1) `div` 2)) (tail (tail p)), let sg = (sf-1) `div` 2]
ghci> take 100 p'
[(2,5),(3,7),(5,11),(11,23),(23,47),(29,59),(41,83),(53,107),(83,167),(89,179),
(113,227),(131,263),(173,347),(179,359),(191,383),(233,467),(239,479),(251,503),(281,563),(293,587),
(359,719),(419,839),(431,863),(443,887),(491,983),(509,1019),(593,1187),(641,1283),(653,1307),(659,1319),
(683,1367),(719,1439),(743,1487),(761,1523),(809,1619),(911,1823),(953,1907),(1013,2027),(1019,2039),(1031,2063),
(1049,2099),(1103,2207),(1223,2447),(1229,2459),(1289,2579),(1409,2819),(1439,2879),(1451,2903),(1481,2963),(1499,2999),
(1511,3023),(1559,3119),(1583,3167),(1601,3203),(1733,3467),(1811,3623),(1889,3779),(1901,3803),(1931,3863),(1973,3947),
(2003,4007),(2039,4079),(2063,4127),(2069,4139),(2129,4259),(2141,4283),(2273,4547),(2339,4679),(2351,4703),(2393,4787),
(2399,4799),(2459,4919),(2543,5087),(2549,5099),(2693,5387),(2699,5399),(2741,5483),(2753,5507),(2819,5639),(2903,5807),
(2939,5879),(2963,5927),(2969,5939),(3023,6047),(3299,6599),(3329,6659),(3359,6719),(3389,6779),(3413,6827),(3449,6899),
(3491,6983),(3539,7079),(3593,7187),(3623,7247),(3761,7523),(3779,7559),(3803,7607),(3821,7643),(3851,7703),(3863,7727)]
ソフィー・ジェルマンは前出のラグランジュ、ルジャンドル、ガウスのほかフーリエやコーシーとも交流があり、ポアソンとの弾性体の研究から弾性理論の先駆者の一人とされています。さらには哲学の分野の研究もあり、その哲学が「社会学の父」と称されるコントに賞賛されていたりと、多才な人物であったそうです。
おわりに
最後に、ソフィー・ジェルマン素数と対になる『安全素数』について少しだけ補足します。この「安全」と呼ばれる理由ですが、RSA暗号のようにその安全性の根拠が素因数分解の困難に依存している暗号と関係しています。RSA暗号は２つの非常に大きな素数の積を用いるのですが、その生成に利用する素数 $p$ が、素因数分解アルゴリズムの１つ「ポラードの p-1 法」に対して耐性がある素数であることから「安全」と呼ばれています。
本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。
本稿の環境
本稿のために使用した環境は以下となります。- macOS: Sonoma 14.5 (chip: Apple M1)
- GHCup: 0.1.30.0
- GHC: 9.6.4
最後までご一読いただきまして有り難うございます。
（●）（●） Happy Hacking!
/"" ＿＿""＼