素数を見つけたからと言って、あるいは、素数でないことが判明したからと言って、何も変わらない。私の前には、やらなければならない仕事が、相変わらず山積みになっている。 ―― 小川洋子『博士の愛した数式』1
Lone Mersenne Hunters とは
Lone Mersenne Hunters(LMH) は、メルセンヌ数の素因数を見つけ出そうという試みである。メルセンヌ数とは、$M_q=2^q-1$の形の自然数のことで、特に$M_q$が素数のとき、メルセンヌ素数と呼ばれる。メルセンヌ数にはLucas-Lehmerテストと呼ばれる確定的な素数判定アルゴリズムが存在するため、最近の大きな素数ランキング上位は軒並みメルセンヌ素数である。このメルセンヌ素数を見つけようという分散コンピューティングプロジェクトがGreat Internet Mersenne Prime Search(GIMPS)なのだが、Lucas-Lehmerテストでは素数か合成数かは分かっても、合成数のとき「素因数は何か？」という情報は何も得られない。そこで、既にメルセンヌ合成数と判明したメルセンヌ数に対して、具体的な素因数を見つけようというのが、LMHの目的である2。
ここまで説明すると、大抵の人には「何のためにそんなことをするの？」という疑問が浮かんでくる。メルセンヌ数の素因数が分かったところで、お金が貰えるわけでもない3。あるいは、世界のどこかにいる誰かが救われるわけでもないし、未来の数学者たちから感謝されることもないだろう。「何のため」と訊かれれば、純粋に「自己満足のため」と答えるしかない、まったく不毛な営みだ。
そういう理由で、LMHに取り組む人は極限られている。そもそも素数に興味を持つということ自体、一般人には到底理解できない嗜好であって、それでもメルセンヌ素数を探索する人たちはそこそこいるが、LMHに取り組もうとする人となるとさらに限定されるのだ。
ソフトウェアの導入
素因数を発見するアルゴリズムは複数あるが、ここでは最も原始的な試し割の方法を紹介しよう。試し割は、GPUを使った方が圧倒的に速く、コスパも良いので、GPUの利用が強く推奨されている。メルセンヌ数の試し割をGPUで行うソフトとして次が存在する。
- Mfaktc (nvidia)
- Mfakto (AMD)
- Mlucas (その他)
ここではMfaktcを紹介する。
- サイトから最新版をダウンロードする。
- 適当な場所に解凍し、(windowsなら)exeファイルを実行すれば動き出す。
プログラムは動き出すと、同じフォルダのworktodo.txtにあるタスクを処理し、results.txtに結果を書き込む。プログラムの実行中にタスクを追加したい場合は、worktodo.addにタスクを書き込んでおくことで、定期的4にworktodo.txtに取り込まれる。
タスクを選ぶ
試し割の現状は ここ から確認できる。基本的に、$2^b$まで試し割が完了していれば$b$の列にカウントされている。興味がある範囲をクリックしていくと、www.mersenne.orgのページに飛ぶので、Output TF worktodo formatにチェックを入れて、数値を指定しGet Dataを押すと、worktodo.txtに指定するフォーマットでタスクが表示される。タスクのフォーマットは、
Factor=N/A,q,b,c
という形式であり、これで$M_q$を$2^b$から$2^c$まで試し割をするタスクとなる。これをworktodo.txtあるいはworktodo.addに貼り付ければよい。results.txtに書き込まれた結果を、 ここ に貼り付けることで提出することができる。
タスクの実行時間を見積もるには、GIMPS内で使われているGHz-daysという単位が一定の指標になる。$M_q$を$2^{b-1}$から$2^b$まで試し割する計算量は、
1680C \times 2^{b-48} / q \mbox{ [GHz-days]}
と、計算される。ただし、
C =
\begin{cases}
0.016968, &\mbox{if}& 65 \le b\\
0.017832, &\mbox{if}& 63 \le b \le 64\\
0.011160, &\mbox{if}& b \le 62
\end{cases}
である。よって、自分が実行したいタスクのGHz-daysを計算し、自分のGPUが1日にどのくらいGHz-daysを稼げるかを知っていれば、1日に何タスクを実行できるかが分かる。自分のGPUが果たして1日に何GHz-days稼げるのか、というのは個々のGPUの性能に依る。参考までに、私の場合、GeForce GTX 1650 で1日に大体900[GHz-days]台が稼げている。