114514素数発見計画(part1)
すまん、15日もブログ更新滞らせる者、おる？
俺やで、どうも久しぶりです。
謎のタイトルですけど、114514に関連する大きい素数を見つけようという計画です。
前提「素数とは何か」
ある自然数において、1とその数でしか割れない数です。ただし1を除く。
（例）2,3,5,7,11,13,17,19,23 全て約数の数は2になります。
現在既知の巨大素数
巨大素数ランキングの上位を占めているほとんどが「メルセンヌ素数」で、2^n-1（nは自然数）という形で表されるものです。
といっても、別段深く考える必要もなく、2^2-1=3(素数) , 2^3-1=7(素数) , 2^4-1=15(合成数)…と調べれば素数がいつか見つかるわけです。
2^n-1を計算して合成数か素数か判定するのは限界があります。1000桁程度ならまだ計算できるかも！！だけど、10万桁うんち。
そこで、様々な素数判定をかけて素数確定か合成数確定か、PRP（おそらく素数）か、判定するわけです。
余談ですけど、メルセンヌ素数は無限にあるかまだ分かっていません。素数は無限にあることが証明されています。
さて、現在既知の一番大きい素数は、2^74207281-1で、22,338,618桁です。
しかも、まだ新しく、2015年9月に発見されました。
その9年前の2006年での最大素数は、9,808,356桁
1996年は420,921桁、1986年は65,050桁、1976年は6,002桁…現代はすごい進化ですね…
巨大素数発見方法
メルセンヌ素数はGIMPSという団体によって日々150,000gHzを使って探索されてます。
個人で探索するのなら、俺の使ってるふるいがけとPFGWをオススメします。
ふるいがけ
https://primes.utm.edu/programs/NewPGen/
PFGW
OpenPFGW download | SourceForge.net
どちらも英語がわかるならいけるかも
NewPGenはふるいがけで、100万の自然数から小さい素数で割れる合成数を見つけ出し、素数候補を残します。後半は時間がかかるので、途中でやめてOKです。たくさんの素数の形から選んで、変数を代入すれば勝手にやってくれるので便利。
PFGWはPRP Testという素数判定を行います。素数候補が何個がでてくるはずなので、
そこから片っ端から素数判定を行います。1000桁程度ならどのPCでも一瞬、10万桁以上は結構キツイ（数分以上）です。
なお、a*b^n±1以外で表される自然数はPRPしかでない（素数確定ではない）と思ってください。
やってみます
まずメルセンヌ素数を見つけてみましょう。
k.b^n-1 with k fixedで、base:2 k:1 nmin:2 nmax:任意でメルセンヌ素数の候補が絞られます。
もうメルセンヌ素数はわかってるので面白みはないですが、一応やってみます。（n=10000)まで
まず絞り込みます
20分の1くらいですかね。1分で10000個→520個まで絞り込めました。
PFGWでファイル名のパス（俺の場合はC:\USER\...（省略）…tage\1145141project201708）を入力
結果…
10秒くらいで終わって草
3-PRPと出たらかなり素数の確率が高いです（ほぼ確定）
この場合、2^31-1 ～ 2^10000-1のメルセンヌ素数全部がPRPになります（まだ不確定）
Wikipedia見ればいまでたこれらのPRPは全部素数だとわかりますが…
自身のPCでも素数確定テストができます。
上のコマンドラインに「pfgw -q(自然数) -tc」と入力すると確定かPRPかどっちかでます。どちらでもない場合、複合と表示されます。
pfgw -q1*2^9941-1 -tc
(自然数) is 3-PRP →-tcが抜けている可能性
Error opening file (自然数) →-qが抜けています
(自然数) is PRP in (テスト)(テスト) →おそらく素数。
巨大素数の発見難度
http://www.geocities.jp/turbo_us_p/prime/resource.html
このサイトが一番詳しいです
1GHzだと、1個の素数発見にかかる平均時間は1000桁でおよそ8秒、15000桁ではおよそ8時間、10万桁ではおよそ97日、100万桁ではおよそ273年です…て、ちょっと～帰らないで～！
今は個人の巨大素数発見プロジェクトを始動させてます
もちろん、1日で終わらせる気はありません。114514^n+810931はn=22000(111295桁時点）で挫折しました（1個あたりにかかる時間はそんなに食いませんが、何日も見つからなくて怖かったんです。それに、+810931だとPRP判定しかでなくて、ちょっと物足りない気持ちがあります）
現在は、114514*2^n-1を始動させてます。名付けて、ジュッセンパイヤー素数！！
昔の発見PRPはぽいぽいっとすててしまいます
↓
114514^22+810931
114514^36+810931
114514^66+810931
114514^1048+810931
114514^2748+810931
655237*114^514±1 (双子 1064桁）
↑発見した中で一番大きい双子素数です。もっと大きいのもいけますよ。
10753972*11^4514+1 (4708桁)
↑一番最初に発見した4000桁超えの素数。
386386386131655*386^386+1 (10104桁）
↑386を使った1万桁の巨大素数
114514^2748+810931 (おそらく素数 13902桁)←非常に高い確率で素数
↑自身が発見した最大の素数（22日現在）
