GIMPS メルセンヌ素数1 概要

2015年9月17日、49番目のメルセンヌ素数M74207281が発見された(GIMPS)。2233万桁にも及ぶという。

発見者はセントラルミズーリ州立大のCurtis Cooper教授(GIMPS ID:curtisc)。GIMPSプロジェクト全体で15個発見され、うち4個は教授の成果だ。

GIMPSのランキング(Reports-Top Producer-Totals Overoll)のcurtiscを見ると、Total GHz Days=5778441.966(2016年6月2日時点)と、GIMPSプロジェクト内でもダントツの計算量で貢献している。

(Current progress-Recent Cleared)をcurtiscでソートしてみる。教授のマシンの結果が連日30台ほど並ぶ。LL判定は計算量が多く、時間がかかるはずだ。同時に数100台が動いているのだろうか。


GIMPSプロジェクトでは、新しいメルセンヌ素数の発見に3,000ドル、1億桁以上の発見に50,000ドルの賞金を出している。１つでも発見できる確率は25万分の1程度らしい。マシン費用どころか電気代もペイできないので、賞金で利益を出すことは不可能だ。
何よりメルセンヌ、オイラー、リュカとともに名を残せることが魅力なのだろう。

メルセンヌ数は、Mn=2^n-1の形で、2進法で1がn個並んだ数だ。
nが合成数(p x q)の場合、Mnは(2^p-1)(2^(q-1)p+2^(q-2)p+...+2^2p+2^p+1)のように因数分解できるので、メルセンヌ素数の探索は指数nが素数の場合に限る。しかし、素数全体を探索するのもあまりにも膨大だ。他に何か制約がありそうだが、GIMPSの実行結果を見る限りでは、指数nは素数を総当りで試すようだ。

探索は計算量が少ないアルゴリズムから順番に実行してゆくらしい。
TF-LMH -> PM1-R -> TF -> PM1-S -> PM1-L -> ECM -> LL(1st) -> D(LL double check) ->PRP(unimplemented)

PRP(unimplemented)のところがよく判らないが、D(LL double check)を通過したものがメルセンヌ素数候補となり、さらに他のアルゴリズムで検証されるのだろう。発見者となるためにはDを実行するべきと思われる。

ちなみに1億桁はM332,192,831以上であり、M332,192,831はLL(1st)までを完了している。
最大、GIMPSはp≦999,999,999、約3億桁までのメルセンヌ素数を発見できる可能性がある。

タグ：素数 GIMPS メルセンヌ