過去最大の素数発見・13万人参加し検算

このエントリーをはてなブックマークに追加
95名無しさん@お腹いっぱい。:01/12/10 09:19 ID:xs2QazGw
ばかばかしい
算数マニアだけでやってろ!
9691じゃないけど:01/12/10 09:21 ID:ENaU0ckJ
97名無しさん@お腹いっぱい。:01/12/10 09:23 ID:1vpAOsYx
数学専攻の方は公開鍵暗号について勉強してください。
98「音読み」は「邪魔」である:01/12/10 09:23 ID:K3mz3BGj
「音読み」は「邪魔」である
http://nara.cool.ne.jp/mituto   
99名無しさん@お腹いっぱい。:01/12/10 09:28 ID:t0seNV0l
> 90
マジで数学専攻?!米国ではNSAとかが90年代半ば以降大量の
数学者を雇っているというのに!!もともと整数論なんて
金にならんと皆思っていたし,NTTの研究所などでもそう
思っていたんだよね.民営化から徐々に時間が経つにつれ
基礎研究がやりにくくなっていた時に整数論をやっていた人間が
急に脚光を浴びた!!

> 94
君の問題は根本的にRSAの原理が分かっていないところにあるんじゃないだろうか?
素因数分解には時間がかかる,大きい素数同士をかけた場合これを
求めるのはとーっても大変,というのが根本原理.素因数分解の困難性は
お分かり?
100名無しさん@お腹いっぱい。:01/12/10 09:36 ID:BC3Uqa/5
いつかどこかで素数が無限にあることを証明せよなんてクイズを聞いたような。
2からnまでの全ての素数をかけて1を加えた数をMとすると
Mは素数であるかnよりも大きい素数の積であるから(QED)
ってのが答えだったと思う。このニュースを聞いて思い出したのはこれくらいかね。
101黒尾寛:01/12/10 09:40 ID:dIa6Uv4j
自然数論について脚光があたっていたらなあ。
素数の一意性が暗号のもつ一意性と合致するから、素数は
暗号に必要なんですよ、って感じだったかな。
102厨房:01/12/10 09:47 ID:KIKjzEQC
こんなに有名な素数を暗号に使ってもあまり意味無い気がするのですが?
103名無しさん@お腹いっぱい。:01/12/10 09:59 ID:ENaU0ckJ
>>102 桁数は発表されてるようだけど、実際の値も発表したのかな?
104103:01/12/10 10:00 ID:ENaU0ckJ
よく見たら”2の1346万6917乗引く1”って書いてあるね。鬱
105広末涼子(本物):01/12/10 10:04 ID:OkCclFE+
11→1+1=2 37→3+7=10→1+0=1 583→5+8+3=16→1+6=7
上の2、1、7のような解をΣ数と定義する。

素数を6乗まで累乗してその値をΣ数変換すると・・・

素数
N (ΣN)1(ΣN)2(ΣN)3(ΣN)4(ΣN)5(ΣN)6
――――――――――――――――――――――――――――――
 1 1 + 1 + 1 + 1 + 1 + 1 → 6
2 2 4 8 7 5 1 → 9
3 3 9 9 9 9 9 → 3
5 5 7 8 4 2 1 → 9
 7 7 4 1 7 4 1 → 6
11 2 4 8 7 5 1 → 9
13 4 7 1 4 7 1 → 6
17 8 1 8 1 8 1 → 9
19 1 1 1 1 1 1 → 6
23 5 7 8 4 2 1 → 9
29 2 4 8 7 5 1 → 9
31 4 7 1 4 7 1 → 6
37 1 1 1 1 1 1 → 6
41 5 7 8 4 2 1 → 9
43 7 4 1 7 4 1 → 6

以上、3を除く総ての素数は
黒幕として6,9を孕む!
              Cecil Balmond 著
             Number 9 より抜粋
106名無しさん@お腹いっぱい。:01/12/10 10:06 ID:7iJLfWnu
 >>90の疑問はもっとも。

 暗号の話を持ち出した人間は「RSA方式の公開鍵暗号には素数が用いられる」
とちゃんと書くべき。他の方式の公開鍵暗号や秘密鍵暗号には素数なんて必要
ない。

 また追記するとこんな巨大な素数はRSA暗号に必要なし(というか全く実用
的ではない)。せいぜい数百桁程度で十分。
107広末涼子(本物):01/12/10 10:07 ID:OkCclFE+
あっ、ズレた
108名無しさん@お腹いっぱい。:01/12/10 10:07 ID:6lENjWOr
スゲー。ヒロスエが来てる。
109名無しさん@おっぱい。 :01/12/10 10:16 ID:4+pJDCHr
これで
正「2の1346万6917乗引く1」角形が、
定規とコンパスだけで作図できる最大数の正多角形になるのか。
110名無しさん@お腹いっぱい。:01/12/10 10:26 ID:QduIlsBu
よく解らないが2で割れないこととはわかる
111 :01/12/10 10:38 ID:M4Qd/YWD
2の1346万6917乗引く2 でも割り切れないだろ?
112 :01/12/10 10:59 ID:3zru2D3E
この手のニュースがあるといつも思うのだが、「それがどうした?」。
これって何かの役に立つのか?普通発見って言うと何かしら役に立つものだが、
素数発見はちっとも役に立たないだろ。無限にある素数を発見した事がそんな
にスゴイのか?と思ってしまう。発見の仕方も努力や才能を発揮した事による
物ではなく、単にコンピュータの計算能力向上によるものであり、全く評価する
部分が無いと思う。
113LAX:01/12/10 11:17 ID:Kxkheq+t
AさんとBさんがいたとして、
Apublic()は公開されている。
Bpublic()は公開されている。
Aprivate()はAさんしか知らない
Bprivate()はBさんしか知らない
Xprivate(Xpublic(message))=messageは簡単に計算できる。

AさんからBさんに,Bさんの公開鍵を使って暗号化したもの
Bpublic(平文)にさらにAさんのプライベートキーで署名を加えた
暗号文=Aprivate(Bpublic(平文))
という暗号文を送る。Aさんは当然Aprivate()を知っているし、
Bpublic()は公開されているから、これで暗号文は組み立てられる。

暗号文を受け取ったBさんは、Aさんの公開鍵を使って
Apublic(暗号文)=Apublic(Aprivate(Bpublic(平文)))
=Bpublic(平文)になって、Bprivate(Bpublic(平文))=平文。
めでたし。Aさんが送ったもので第三者が改ざんしていないことも
Aさんの署名で展開できたことから確認できた。
ここまでが二重公開鍵暗号鍵の仕組み。

鍵そのもの強さ(暗号の強度)はここから。
Xprivate->Xpublicは簡単に求められるけれど
逆関数にあたるXpublic->Xprivateは簡単に求められない関数を
見つけるのがミソ。ここで素数の掛け算と素因数分解
の関係を応用したわけ。落とし戸(一方向)関数はこの他にもいろいろ
ある。最近は楕円系が流行りらしいDEATH
114LAX:01/12/10 11:27 ID:Kxkheq+t
>>112
まぁ計算能力の向上の尺度を示した意味はあるじゃん。
それから元記事によれば「グリッド・コンピューティングと呼び、暗号の
解読や遺伝子解析などに利用されている」って言ってるわけで、
計算アルゴリズムの応用範囲を実証したって点でも意味はある。
115名無しさん@お腹いっぱい。:01/12/10 11:37 ID:89xoidb4
>114
たぶんそうやって書いても、>>112には分からないと思う。
116名無しさん@お腹いっぱい。:01/12/10 12:12 ID:h1XBygff
今のコンピュータを20万台使えばどのくらいの処理ができるかっていうのが
分かっただけでも意味があるよね。
117名無しさん@お腹いっぱい。:01/12/10 12:36 ID:t0seNV0l
> 114
このメルセンヌ素数発見は分散コンピューティングの応用(と言っても本来の
分散メモリ型並列計算機によるものというよりその概念の拡張)で現在
進められているGlobusなどのGridコンピューティングとはちょっと違う気が
するし,Gridというには特にヘテロ環境における分散計算について技術的に
何かやっているわけではない.5年ほど前にメルセンヌ素数が新たに
見つかったときと今回は全く同じメソッドだと思うぞ.この5年前のメルセンヌ
素数の時に以前のものと何が違ったかというと,スパコン回すよりも多くの
PCで手分けして解いたほうが良い問題があることを実証した点.ちなみに
多くの科学技術計算がスパコンより分散で解いたほうが良いとは思えないが,
皆でやったほうが良い問題もある.それを5年前に示したのがその時の成果.
だから,”蟻が象に勝った!”と話題になった.今回は,それを推し進めて
規模を広げただけ...

また,計算アルゴリズムの正しさはルーカス・レーマーテストの正しさと
同意でありGridであるか分散であるかということからすら別の問題.

単純に,116の感想が率直だし正しいと思う.
118:01/12/10 13:06 ID:rTUKqzdx
後の世代で活用される発見もある。
119ひろゆき:01/12/10 13:19 ID:JqbV8WcE
既存の暗号化技術って素因数分解に根ざしたものが多いわけだから、
でかい素数ができるほど堅い暗号がつくれると思われ、、、
120いまどきの数学専攻はこの程度のバカしかないようです。:01/12/10 14:05 ID:xcsqBO+8
90 :  :01/12/10 01:46 ID:2BGWqTpw
これでも一応数学専攻なんだが、暗号作るのに素数がいるというのはよくわからんなあ。
絶対解けない暗号って、お互いに同じ本(たとえば聖書や電話帳)を持って、それをキーワードにしたらいかんの?
スタートの暗号文は1頁目を利用し、次の使用頁はその暗号文中に示しとけば良いと思うのですが・・・。
121名無しさん@お腹いっぱい。:01/12/10 14:21 ID:XtjQcGH6
数学専攻でもないただのプログラマですが、
長年日の目を見なかった数学理論から、JPEG2000が生まれたり
ゲームソフトに広く使われてる乱数発生器が生まれたりするわけで。

ま、先行投資みたいなもんでしょ。
即効性求めちゃダメだって気がするのねん。

#あと>>90は俺から見てもバカ。
122名無し:01/12/10 14:32 ID:aIiE2KbW
>>90
暗号表(それがあれば解読が簡単な鍵)を持たせるやり方じゃ、
暗号表を奪われたらおしまいでしょ。
だからたくさんの人間に持たせることはできない。
ましてやネット上のセキュリティシステムなんかに絶対利用できない。
そのために公開鍵暗号ってものがあるの。わかる?
公開鍵f(a)→bがわかっても復号鍵f(b)→aを探すのが不可能に近い暗号。
復号鍵は一箇所に厳重保管しておく。これで安全性は限りなく高まる。
123名無しさん@お腹いっぱい。:01/12/10 16:25 ID:+V4+K56z
逆に言うと、これくらいのコンピュータを集めると、とてつもない
桁数の暗号も解けちゃうという事?もしかして。
124106:01/12/10 18:44 ID:7iJLfWnu
>>121-122

 いや、だから>>90は「暗号作るのに素数がいるというのはよくわからんなあ」
と書いてるだけでしょ?誰も「公開鍵暗号」に限定して書いて無いし、ネット上
でのセキュリティなんて論じてない。

 実際秘密鍵暗号やRSA以外の公開鍵暗号にはアルゴリズムに素数使わない訳だ
し、一方的に>>90を叩くのはちょっとアンフェアでは?

>>123

 力業で解けない暗号はありません。ブルートフォース法は最も一般的な暗号
解読法の一つです。
 
125 :01/12/10 20:32 ID:wR5T1iaZ
>>124
90はあまりに古典的な暗号システムをまるで自分がはじめて
気づいたかのように持ち出し、これがあれば巨大素数使用の
ものを含む最新暗号などまるで不要であるかのような書き方
をしているところがとてもバカ。
126 :01/12/10 20:35 ID:KFzMUC+A
このスレが立ってはや2日すぎたけど
この話題あいかわらず数学板にはほんの一言も出てこないね。
127123:01/12/10 23:31 ID:wgGkXHjg
>>124
や、ふと思ったんだけど、白血病プログラムみたいなのに、
暗号解読のためのロジックを埋めこんでCPU時間の一部を
借用するようにしたら、気づかずに暗号解読の手伝いをさせ
られていたなんて事がおきてしまうのでは?

だとすると、「十分に強固」とは言えなくなっちゃうのかな?
128 ◆GEDOw/Q2 @外道φ ★:01/12/11 00:28 ID:???
>>126
スレ立ってる

過去最大の素数発見・13万人参加し検算
http://cheese.2ch.net/test/read.cgi/math/1007811571/
129名無しさん@お腹いっぱい。:01/12/12 00:03 ID:Mb3hqnZ8
age
130名無しさん@お腹いっぱい。:01/12/12 00:21 ID:VC3hXonR
これがその素数。4MBもあるYO!
http://www.mersenne.org/prime5.txt
131ど素人:01/12/12 01:55 ID:ZshrG2jN
こういう暗号はどうですか。古典法かもしれませんが(w

10000個(仮)の数字を二組(A&B)送る。(どうせ盗聴されるだろうからオープン)
あらかじめ決めておいた、何桁目をどういう順番で使うかという情報を元にAとBそれぞれから100個程度の数字を得る。
Aの数字を元に得た暗号表(新聞、ドメイン名等)の指定頁を使い文字列(指令等)を得る。
Bの数字からも同様の作業を行い次回の暗号に適用される何桁目をどういう順番に使うかの情報を得る。
以下くり返し
132 :01/12/12 01:58 ID:vHYSaeVu
>>131

古典的だね。
正直、何桁目をどういう順番で使うかという情報が知られないわけはないと思われ。
133名無しさん@お腹いっぱい。:01/12/12 02:01 ID:mgPIbT+8
言いたい事はよく分からんが、とにかくすごい自信だ。
134名無しさん@お腹いっぱい。:01/12/12 04:49 ID:deRwsWcm
>>131
暗号アルゴリズムとそれ以外の方法の複合となっているね。
解読した文をそのまま使うのではなく新聞などの情報にてらして
意味を取るというのは、たとえば「ニイタカヤマノボレ」という文章を傍受しても
それだけでは何を指すかわからないというのと同じで隠語テーブルを使う方法だね。

そういう要素を除いて、Aの数列の部分が平文(保護したい内容そのもの)に
対応すると考えると、これは単なる射影と置換の組み合わせだと思う。
135 :01/12/12 05:11 ID:XNbUpbb1
で、本題だが、、
大きな素数発見していったい何の意味があるんだ?
136名無しさん@お腹いっぱい。:01/12/12 05:16 ID:+ze/R2H7
結局暗号化っていうのはデータのエントロピーをできるだけ増大させればいいってことかな。
137175828273:01/12/12 05:30 ID:iW8DjGY7
詳しくはこれに書いてあります。エニグマやカエサルシフト。
ちょっと高いけど。
特に361〜372頁。

暗号解読 ロゼッタストーンから量子暗号まで / サイモン・シン/[著] 青木薫/訳
新潮社
2001年7月発行
493,16P 20
ISBN: 4-10-539302-2
価格: 2,600円(税別)
138名無しさん@お腹いっぱい。:01/12/12 05:40 ID:Ceq9FcCB
サイモン・シンって、あの「フェルマーの最終定理」書いたジャーナリストだね!
139名無しさん@お腹いっぱい。:01/12/12 05:46 ID:U91MBCok
卒論おわんねー。
140175828273:01/12/12 05:51 ID:iW8DjGY7
138さんへ
そうです。反応なかったらどうしようと思っていました。
今、フェルマーの方を読んでます。
141名無しさん@お腹いっぱい。:01/12/12 05:52 ID:POO96FEU
偏微分方程式や関数解析なんかの純解析系を専攻してる奴は
素数のことなんて知らんぞ。90くらいでぜんぜん普通。
142名無しさん@お腹いっぱい。:01/12/12 06:16 ID:9f9BNtGG
素数の研究には,解析的な知識も必須だが,逆はないもんね.
143     :01/12/12 06:20 ID:Na+Jw9p3
だいぶ前に
「フェルマーの定理」っていう本読んだけど感動したよ。
数学的な意味はサッパリわからんけど。
144名無しさん@お腹いっぱい。
oge