吟遊詩人の素数探索その1〜メルセンヌ素数について〜

どうも、さっさと1億桁の素数を見つけて早期退職したい吟遊詩人です。

ネット上で死なないために素数を探し始めたわけですが

https://ginyusizin.com/2019/11/09/0014/

基本的に巨大素数を見つけようとした場合、それはメルセンヌ素数がターゲットになります。

メルセンヌ数(メルセンヌすう、: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。2進数表記では、n 桁の 11⋯11 となる。

出典: フリー百科事典『ウィキペディア(Wikipedia)』:メルセンヌ数

現在発見されている最も巨大な素数はM82,589,933でやはりメルセンヌ素数です。10進数の桁数は24,862,048で、これより約5倍大きい素数を見つければ10万ドルもらえるわけですね。(たしかM77,232,917を発見した人はFedEx社員だった気がする。)

なぜ発見された大きい素数がメルセンヌ数ばかりかと言うと、リュカ・レーマーテストという高速な素数判定法があるからなんですよね。

このメルセンヌ数、いくつか大事な性質があります。

基本的な性質

Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]:2ab − 1 = (2a − 1)(1 + 2a + 22a + ⋯ + 2(b−1)a).

対偶命題n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。

出典: フリー百科事典『ウィキペディア(Wikipedia)』:メルセンヌ数

nが合成数ならば、Mnも合成数なのですが、2進数で書くとわかりやすいと思います。

図のように、2進数表記で1が合成数個並んでいるとしたら、その約数個の1の束と、別の約数個の1の間に0を挟んだものに分解できるというわけですね。

Mpが素数ならpも素数ですが、pが素数でもMpは素数とは限りません。最小の反例はM11です。

全てのpに対してMpが素数であってくれればM_Mpとすることでいくらでも巨大な素数を見つけることができたのですが、そうはいかなくなりました。

2,3,7,13などはメルセンヌ素数を与える素数なのに対し、11はメルセンヌ素数を与えない素数になります。メルセンヌ素数を与える素数の法則のようなものが見つかると良いのですが……。

メルセンヌ数の未解決問題

メルセンヌ数に関する未解決問題は以下のとおりです。

未解決問題

・メルセンヌ素数は無数に存在するか?

・素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?

・平方因子を持つメルセンヌ数 Mpp は素数)が存在するか?

n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 105 に対してこの予想は正しいと確認されている[43]

1.Mn が素数

2.n = 2k ± 1 または 4k ± 3

3.(2n + 1)/3 が素数

出典: フリー百科事典『ウィキペディア(Wikipedia)』:メルセンヌ数

1つめと2つめの予想は少なくともどちらかは正しいと思います。

吟遊詩人予想

さて、今後素数探索をしていくに当たって、闇雲に探すのもあれなので、いくつか予想を立てて行きたいと思います。

吟遊詩人予想

  1. M_2147483647は素数である
  2. M_170141183460469231731687303715884105727は素数である
  3. MP(0)=M_2, MP(n+1)=M_MP(n)としたとき、MP(n)はメルセンヌ素数である
  4. MP(0)=M_5, MP(n+1)=M_MP(n)としたとき、MP(n)はメルセンヌ素数である

とりあえず一番上の予想だけでも当たれば1億桁超えの素数なので、10万ドルGETですね。(数ギガの剰余算を20億回近く繰り返す必要があるのか……)

次回は実際にどのように判定していくのか、リュカ・レーマーテストのお話をしたいと思います。

おまけ

最近素数の話題で双子素数問題が解かれたというのがありましたね。

ちょっと前に600離れた素数が無限に存在する証明がされていましたが、

いやー数学の進歩ってすごいですね。

私も素数探索を通して理論の方も勉強して、少しでも理解できるようになりたいです。

つづく

吟遊詩人の素数探索その1〜メルセンヌ素数について〜” への1件のフィードバック

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中