理系の方、メルセンヌ素数について詳しく教えて下さい。

http://www.cnn.co.jp/science/CNN200601050008.html
こんなニュースを読みました。不思議です。
ヒトゲノムのどれが解読、とかいうニュースなら何かとっても役に立ちそうなことはわかりますし、素数の意味も一応わかります。
でもメルセンヌという人がどうしてそんなことを思いついたのか、なぜ今43番目なのか、どうしてこれが記事になるほどスゴイのか、ちんぷんかんぷんです。どうかど素人の私にも得心のいくよう、教えて下さい。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/01/10 23:06:07
  • 終了:--

回答(5件)

id:kaoru290 No.1

kaoru290回答回数195ベストアンサー獲得回数02006/01/10 23:48:41

ポイント16pt

http://www.hatena.ne.jp/1114503126

人力検索はてな - 量子コンピュータが出来るとRSAなどの素数暗号が簡単に解けてしまい、時代遅れになると聞きました。その理由について教えてください。..

以前のはてなにこんな質問がありました。要は、ものすごく大きい素数は現在のコンピュータで求めるのは大変だから、スゴいんです。

id:eio

素数ってのは暗号関係に使われるものなんでしょうかね?私自身は2とか36とか色々割り切れる数字が好きなので、43番目の素数と聞いて「どんな物好きなのか」と思ったのですが、見当違いのようで・・・以前のURLありがとうございました。これから熟読します。

2006/01/11 01:00:14
id:aska186 No.2

aska186回答回数158ベストアンサー獲得回数02006/01/11 00:02:01

ポイント16pt

http://pcweb.mycom.co.jp/news/2002/12/06/20.html

円周率計算の世界記録が更新される 新記録は約1兆2,400億桁 (MYCOMジャーナル)

直接の答えになっていないかもしれませんが、いくつか考えられます。

・数学者というのは、そういう(ある意味)どうでもよいことに興味を持つ人種である...

・現実的な面…メルセンヌ素数という数学の概念を使った、コンピュータの限界への挑戦、という側面があると思われます。

円周率の記録の場合もそうですが、単に、同じプログラムをコンピュータで走らせ続ければ次の数がでてくる、というわけでもないわけでして。

コンピュータの性能の向上、アルゴリズム(計算式)の工夫、プログラミングの工夫などなど。様々な技術的な工夫という副産物がある可能性があり、そこで得られたことが、思わぬ何か別の場面で有効に利用できる場合があります。

id:eio

そう!円周率もそうなんですよ!そんなに追及してどうにかなるの??2次元で中心から等距離にある点の集合が円ってだけじゃだめなの??なぜ???と思っていました。っていうか今も思ってます。限界に挑戦するアスリートみたいなものなんでしょうか?

2006/01/11 14:37:14
id:EdgarPoe No.3

EdgarPoe回答回数266ベストアンサー獲得回数462006/01/11 14:15:19

ポイント16pt

http://ja.wikipedia.org/wiki/メルセンヌ数:detail]

初めまして。E.A.Poe(知のくずかご)と申します。


主題:メルセンヌというとメルセンヌ型素数について


小生はバリバリ文系で、しかも数学はあまり詳しくないのですが、一応回答してみます。

なお、小生の回答は話を面白くするために「講釈氏 見てきたような ウソを言い」という面がありますので、多少の間違いが含まれている場合があります(笑)。


--

メルセンヌという人は、本職は僧侶でしたが、なぜか数学や物理にわりと詳しい人でした。

しかも、人当たりが良かったのか、当時たくさんの一流の科学者・数学者と仲が良かったようで、人々を修道院に呼んでパーティ(というか発表会)のようなものを開いたり、

パーティにこられない人とはしょっちゅう手紙をやりとりしていました。

当時は「学術論文掲載雑誌」などというものはなかったので、メルセンヌさんは言わば「個人営業のボランティア『学問交流会』開催者」という立場にいたようです。

メルセンヌさん自身は特に数学や物理の才能に秀でていなかったものの、こういうことをやっていたので歴史に名が残ったのです。うまいやり方ですね(笑)。


--

で、メルセンヌ素数の話にうつります。

素数とは「それ以上約数がない数」ということで、整数の中では「もっとも美しい」なんて言う人もいたそうです。どこがどう美しいのかよくわかりませんが(笑)。

で、誰かが「『ある数xを入れると自動的に素数yが出てくる』という式『y=F(x)』を見つけよう(考案しよう)。そうすれば、美しい素数が無限に手にはいるじゃないか」と思い立ちました。

しかし、これは問題の意味はカンタンですが、実際のy=f(x)はなかなか見つかりません。


例えば、アマチュアでしたが(本職は弁護士)超一流の本職数学者を凌ぐらいの天才的数学者フェルマーさんが「『y=2^2^x+1』を使えば(たぶん)無限に素数が出てくるよ」と発表しました。

実際にフェルマー数を見てみると

x=1のとき、2^2+1=5

x=2のとき、2^4+1=17

x=3のとき、2^8+1=257

x=4のとき、2^16+1=65537

と、全部素数です。これに気をよくしたフェルマーさんは

x=5のとき、2^32+1=4294967297

を一生懸命研究し

#桁数が多すぎてまともに割り算をやっていたら絶対ムリです。コンピュータどころか電卓もないし

#きっとそろばんも知らなかったでしょうから

「どうやら素数らしいぞ」と考えて、メルセンヌさんに上述の手紙を出したのです。

しかし、約100年後にオイラーというこれまた超人的な数学者が4294967297=641×6741007と因数分解してしまい、素数でないことを発見してしまいました。

フェルマーさん、残念!


で、メルセンヌさんはこのような事態を何度も目撃し、発想を変えました。

「必ず素数が出てくる式」を作るのは難しいので、先に式「2^p-1=M(pは素数)」を考えました。これは、でてくるMは必ず素数になるという訳ではありませんが、

「Mが素数の時は必ずpも素数である」

ということがわかりました。

#このあたりに完全数の話が入るのですが、よくわからないのですっ飛ばすことにします。

#本職の理系の方、見逃してくださいm(__)m

つまり「とりあえずpに素数を代入してMを計算して、出てきたMが素数かどうか試せばイイ。素数ならラッキー、素数じゃなければ残念!」ということです。

この方法を使っても、pが大きくなるとMはこれまたとんでもなく大きくなるため

#Mの桁数が1000を超えたりします。要するに数字が1000個並んでいるということです

素数探しは大変は大変なのですが、、やみくもに素数を探すよりずっとラクになりました。


さらに大胆なことに、メルセンヌさんは

「この場合、pを『2・3・5・7・11・13・…』と片っ端から試す必要はない。

#実際、p=11のときには、出てくるMは素数にはなりません

私の思うとところでは、Mが素数になるpは、257までの素数のうち『17・19・31・67・127・257』の6つだけだ」

と主張(予想)したのです。メルセンヌさんは証明とかは一切せずに「何となくそう思う」と言っただけなのですが、一流の数学者たちと交流のあるメルセンヌさんの発言ですから

「むむむ…。メルセンヌさんは直感的に素数を見抜く能力でも身につけたのか?」と評判になり、この型の数

「2^p-1=M(pは素数)」を「メルセンヌ数」、出てきたMが素数だった場合を「メルセンヌ型素数」

と呼ぶようになりました。


--

で、後世になってコンピュータの発達などから「メルセンヌさんの予想は本当に正しかったのか?」と検証する人が現れ「2^p-1=M(pは素数)」のpに片っ端から素数を代入してMを求め、今度は出てきたMが本当に素数かどうか判定し始めました。


残念なことに、メルセンヌさんの予想は外れました。

「p=17・19・31・127」の場合のMはたしかに素数でしたが、「p=67・257」は素数ではありませんでした。残念!

しかも、メルセンヌさんが言及しなかった「p=61・89・107」の場合のMも素数であることがわかり、

メルセンヌさんの予想はどうやら50%ぐらいの確率でしか当たらなかったことがわかってしまいました。

#とは言っても、全くでたらめでもなかったところがメルセンヌさんのスゴイところです(笑)


まあ、メルセンヌさんの予想は外れましたが、それでも素数を探すやり方

「『2^p-1=M(pは素数)』のpに片っ端から素数を代入してMを求め、今度は出てきたMが本当に素数かどうか判定する」

方法は今でも行われており、それ以降のp、つまり p=521・607・1279・2203・2281・3217・4253・9689・9941・11213・19937・21701、… 25964951(これで42番目) とどんどん「Mが素数であるようなp」が見つかっています。

今回はこのpの行列がもう一つ長くなり、25964951 のつぎの43番目のp=30402457 が見つかった

#「2^p-1=M(pは素数)」のpに30402457を入れるとでてくるMが素数であることがわかったということで、世界的なニュースになったのです。


--

http://www.amazon.co.jp/exec/obidos/ASIN/406117777X/249-6589939-...

Amazon.co.jp: ゼロから無限へ―数論の世界を訪ねて: 本: コンスタンス・レイド,芹沢 正三

今回の小生の「講釈氏 見てきたような ウソを言い」の元ネタは、この「ゼロから無限へ」です。

小生は中学生の時にこの本を読んで、訳がわからないながら面白いと思い、今でもたまに読み返しています。


もし eio さんがこういう数学の話に興味を持たれた場合は、この本を購入してしっかりと読んでみることをお勧めします。

小生がすっ飛ばした「完全数」の話もちゃんと載っていますし(笑)。


--

かなりウソや間違いも入っているとは思いますが、お役に立ちますかどうか。


PS:小生の回答をご覧になって間違いの指摘をしていただける方や、細くしていただける方がいましたら大歓迎です。その分のポイントはのっかりします。

id:ttamo No.4

たも回答回数175ベストアンサー獲得回数292006/01/11 18:24:09

ポイント16pt

この wikipedia エントリの最初のほうに、いきさつが書いてあります。

そして「未解決問題」があるので、とりあえずたくさん発見してみる

ことに意義があるようです。どんどん計算して、なにかヒントが出る

(あるいは反例があって一挙に解決したりする) かもしれません。


素数をたくさん出すことにはゼータ関数も関連していて、

ゼータ関数は数学の最重要問題「リーマン予想」と関係があるようです。

大きな素数がたくさんあれば、ゼータの謎を解くヒントが

少しは見えてくるかもしれない、ということでしょうか。

ほかにも素数に関連する問題はいろいろあるようです。

で、順番に素数を出すより、とばしてメルセンヌ素数を探すほうが

早く大きな素数を出せるので良いのではないでしょうか。


と、どうも私自身ぜんぜんわかっていないので、

wikipedia のページ紹介ばかりになってしまいました。

ポイントは他のかたにあげてください。

id:eio

やっぱりオイラーさんなんですね。一筆書きのプロ。面白すぎます。でも2個目のURLを見たときは、数式がわかるわからない以前の問題として、読めませんでした。=と+しか。素因数分解と因数分解の違いもわからない私です。かなしいです。

あとEdgarPoeさんにコメント入れたはずが飛んでしまいました。すみません。やっぱりメルセンヌさんよりもオイラーさんに激しく感動しています。Wikiの写真もステキでした。『2^p-1=M(pは素数)』のpに、私も色々入れてみたいと思うのですが、「^」っていうのは何なんでしょうか?こんな私が首をつっこむべきではないような気もするのですが。

2006/01/13 13:24:11
id:p243 No.5

p243回答回数142ベストアンサー獲得回数62006/01/13 01:47:18

ポイント16pt

http://www.cnn.com/

CNN.com - Breaking News, U.S., World, Weather, Entertainment & Video News

URL=ダミー

答えになっているかどうかという点では少し自身がありませんが、このような発見は発見されないと使う事ができないですよね。ニュートンがりんごが落ちるという事から法則を生み出しました。別に数式でどうこういわなくても、落ちてくる物は落ちてくるといってしまえばそれまでだったわけです。しかし、その法則に基づいて機械やロボット、飛行機、宇宙船など様々なものが生み出されてきました。発見は発明の母だったわけです。我々は知恵を持っていますのでこれを誰かが上手く利用するかも知れません。またこのような最先端の発見が普通にニュースで見れるという意味ではCNNも捨てたもんでもないなとおもいます。将来的にはこのような努力をもとに素数を導き出す公式ができ、どんな素数も簡単に見つけられる様になるとその利用方法が広がるかもしれませんよ。

id:eio

なるほど!!!めちゃくちゃ納得できました。素数かどうかを判定する計算式じゃなくて、素数を返す計算式を見つけたら、私もニュースのヘッドラインに名前が載るでしょうか?

2006/01/13 13:27:21
  • id:EdgarPoe
    ニュースになりますよ、きっと(笑)

    歴史的な解説に終始して eio さんの質問の真意をくみ取り損ねたE.A.Poeですm(__)m。

    とりあえず p243 さんの回答でめちゃくちゃ納得されたようなので、良かったですね>eio さん・p243 さん

    >素数を返す計算式を見つけたら、私もニュースのヘッドラインに名前が載るでしょうか?
    ええ、おそらく100%の確率でニュースヘッドラインに載れると思います。

    #リンク先に「素数生成式」がいくつか載っていますが、どうやら
    #>多変数の高次多項式では、全ての素数を生成することができる式がいくつ#か知られている。
    #とのことで、あんまり一般的ではないようです、小生もよくわかりませんが(爆)。
    単純に「nを1から順番に入れていくとどんどん素数を返す式」
    #例えば「f(n) = n2 + n + 41」等。
    #残念ながらこの式はん=41 の時に素数ではなくなるようです
    を eio さんが見つけたら、もう大評判でしょう(笑)。

    --
    なお、補足ですが「『2^p-1=M(pは素数)』のpに、私も色々入れてみたいと思う」とのことですが、^は「べき乗」のことです。例を挙げると
    P=2のとき、 M=(2×2)-1=3(素数)
    P=3のとき、 M=(2×2×2)-1=7(素数)
    P=5のとき、 M=(2×2×2×2×2)-1=31(素数)
    P=7のとき、 M=(2×2×2×2×2×2×2)-1=127(素数)
    P=11のとき、M=(2×2×2×2×2×2×2×2×2×2×2)=2043=23×89(素数ではない)
    というように使うはずです。
    #P=11のときの素因数分解は、電卓片手に少々苦労しました(笑)

    --
    で、例えばP=17の時に素数になるかどうかを判定したいときは、出てきた答えが下記のサイト
    http://www.h7.dion.ne.jp/~konton/sosuu.html
    にあるかどうかを調べてみることがカンタンで面白いと思います。もしなければ、小生のように電卓片手に素因数分解してみるか、それなりの推理力を持って素因数を決定してみてはいかがでしょうか?

    もう一歩進んで、効果的な素数判定方法を調べた上で
    #http://ja.wikipedia.org/wiki/素数判定 が役に立つでしょうか?
    #小生にはちんぷんかんぷんで、お経の文句と変わりません(爆)
    先のサイトの一番大きい素数「999983」を使って「M=n999983 -1」が素数であるかどうか判定するのも、ある意味楽しいかも知れません(?)(笑)。


    --
    最後に、オチを一つ。
    「1776年にオーストリア政府が国費で作った素数表はさっぱり売れなかったので、
    とうとう没収されてトルコ戦争のときの弾薬包みとして使われてしまった」

    やはり、aska186 さんのおっしゃるとおり「数学者というのは、そういう(ある意味)どうでもよいことに興味を持つ人種である」であって、大部分の人はお金を出してまで素数を知りたいとは思わなかったみたいです(笑)。

    まあ、趣味の一つとして素数判定をするのが普通の人の考えだと思いますが、
    ひょっとして「これを誰かが上手く利用するかも知れ」ないと思って未来へのロマンに賭けてみるのもカッコイイかも知れませんね。

    --
    長文失礼しました。それでは…。
    http://ja.wikipedia.org/wiki/素数#.E7.B4.A0.E6.95.B0.E7.94.9F.E6.88.90.E5.BC.8F

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません