[GRID]メルセンヌ素数

スーパーコンピュータやグリッドのニュースに良く出る話題として大きな素数を計算する事が挙げられる。こんな大きな素数をどうやってサーチするんだろう？と思う人も多いはずだ。

さて、大きな素数を求める場合、そのターゲットとなる数のあたりをつけるためにメルセンス素数を使う場合がある。
メルセンヌ素数とは次のことを言う。

ある素数nについてメルセンヌ素数Ｍ_n=2ⁿ-1

nが合成数の場合、M_nは合成数であることが証明されている。そのため、nが素数の時、M_nが本当に素数かどうかをチェックする必要がある。提唱したメルセンヌはnが素数の時は必ずM_nも素数だと考えていたが、それは間違っている事がわかっている。

ところで、M_nが素数かどうか判断するには、一般的な数の素数を判定するよりもずっと簡単に計算することがわかっている。これがリュカ＝テストと呼ばれるものである。そのため大きな数の素数を見つけるためにメルセンヌ素数を利用しているのだ。
リュカ＝テスト

今最大の素数は６３０万桁以上であるが、それはメルセンヌ素数である。また、それはＧＲＩＤを使って求められている。
史上最大のメルセンヌ素数、分散コンピューティングプロジェクトで発見

メルセンヌ素数のような素数になりうる候補の数へのアプローチを考えてみるのも面白いだろう。