« 東京都現代美術館 | トップページ | 海外旅行の懸賞 »

2004.05.27

[GRID]メルセンヌ素数

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

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

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

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

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

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

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

|

« 東京都現代美術館 | トップページ | 海外旅行の懸賞 »

パソコン・インターネット」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/666145

この記事へのトラックバック一覧です: [GRID]メルセンヌ素数:

« 東京都現代美術館 | トップページ | 海外旅行の懸賞 »