メルセンヌ素数

Dec 20, 2011

確率のネタではないですが、小話をひとつ

NtRandでは”Mersenne-Twister”と呼ばれる一様乱数生成アルゴリズムが採用されています。このアルゴリズムで生成される乱数は $2^{19937}-1$ 、実に6002桁という途方もない長い周期をもっています。

さて、この数は”メルセンヌ素数”と呼ばれる一群の数字のうちの一つで、これが”Mersenne-Twister”の語源になっています。

メルセンヌ素数とは、素数のうちで $2^{n}-1$ という形で書けるもののことです。つまりMarsenne-Twisterの周期は $n=19937$ のメルセンヌ素数です。 2001年5月現在、メルセンヌ素数は47個見つかっています。 $n=19937$ のメルセンヌ素数は24番目のものです。

1644年、マラン・メルセンヌさんが $n=2,3,5,7,13,17,19,67,127,257$ がメルセンヌ素数であると主張しました。残念なことに彼は $n=61,89,107$ を見逃していました。

更に残念なことに、、、

1903年、アメリカで行われた数学会でフランク・ネルソン・コールなる人物が発表のため登壇しました。タイトルは「大きな数の素因数分解」。

彼はまず黒板に $2^{67}$ を書き下しました。

$2^{67}=147,573,952,589,676,412,928$

そこから1を引き、そして次に

$193,707,721\times761,838,257,287$

の計算を行いました。その結果は、、、 $147,573,952,589,676,412,927$ ! その間彼は一言も口をきかず、静かに席に戻りました。その後会場は万雷の拍手が沸いたそうです。

メルセンヌさんの主張から250年以上経って、 $2^{67}-1$ が素数でないことが分かったのです。

今では $n=127$ も素数ではないことが分かっています。

Comments are closed.