【ムネムネ会会長】千葉８区桜田義孝スレッド

[過去ﾛｸﾞ] 【ムネムネ会会長】千葉８区桜田義孝スレッド (958ﾚｽ)
上下前次1-新
抽出解除必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞あぼーん

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

392: 02/09/05 23:17 ID:JggUXb/w(1/21)調 AAS
：１３２人目の素数さん：02/08/08 22:24
素数判定は「決定的」多項式時間で可能

だそうである。拡張リーマン予想とかの仮定なしに。
識者のチェックキボンヌ。

外部ﾘﾝｸ[html]:www.cse.iitk.ac.in

このページの上のほうの、"PRIMES in P"

2 ：１３２人目の素数さん：02/08/08 22:26
ふ～ん

3 ：１３２人目の素数さん：02/08/08 23:13
それほど時間かからないってこった。

4 ：１３２人目の素数さん：02/08/09 07:16
因数分解もそうなってくれたらいいのにね。

5 ：１３２人目の素数さん：02/08/09 14:12
なんでこのスレは4つしかレスがないの？
これ、すごいことではないですか？
（数学専門ではないのですが、（コンピュータ専門）
すごい騒ぎになってるのでは？と思ってはじめて
この板に来たのですが）

393: 02/09/05 23:20 ID:JggUXb/w(2/21)調 AAS
6 ：１３２人目の素数さん：02/08/09 14:13
だって意味和漢ねーン唾問、俺馬鹿だから。

7 ：１３２人目の素数さん：02/08/09 14:16
いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね？（つい最近習った）

すごいんじゃないのかなぁ。。。
すいません。俺も詳細は全然わからんが。

Bell Labの研究者もこのインド人の先生のoutputを
検証してみたけど、問題なかったと言ってたらしい。

8 ：１３２人目の素数さん：02/08/09 14:17
うちのパソコンじゃ見れません｡･ﾟ･(ﾉД`)･ﾟ･｡

9 ：１３２人目の素数さん：02/08/09 14:21
っていうかアメリカはいま大騒ぎです。(Stanfordより)

10 ：１３２人目の素数さん：02/08/09 14:21
英語が読めません
ばばーい(･∀･)

394: 02/09/05 23:22 ID:JggUXb/w(3/21)調 AAS
10 ：１３２人目の素数さん：02/08/09 14:21
英語が読めません
ばばーい(･∀･)

11 ：　：02/08/09 14:23
>>4
数学的にはいいんだろうけど、
それ出来てしまうと、コンピュータで使われている暗号が
使えなくなっちゃうよ｡

12 ：１３２人目の素数さん：02/08/09 14:24
ごめん。いまNYTimesか、Washington postの最新記事を
探してるんだけど、どうしても出てこない・・。

今日8日（もう昨日か）の朝は、大学はこの話題でもちきり
でした。>>11 そうなんですよね・・・。

13 ：１３２人目の素数さん：02/08/09 14:31
ありました。NYTimes, 8日付です。
外部ﾘﾝｸ[html]:www.nytimes.com

14 ：１３２人目の素数さん：02/08/09 14:47
スレタイ見た瞬間「渋い所をついたネタスレだなぁ」と思ってしまった。
マジなのかよ。

15 ：１３２人目の素数さん：02/08/09 14:49
マジです。

395: 02/09/05 23:26 ID:JggUXb/w(4/21)調 AAS
16 ：１３２人目の素数さん：02/08/09 14:50
っていうか「渋いところ」っていうより、かなり根幹でしょ。

17 ：１３２人目の素数さん：02/08/09 14:52
>>16
正直、人による。

18 ：gf ：02/08/09 14:54
-------風俗の総合商社・ＭＴＴどこでも-------

〇デリバリーヘルス〇デートクラブ〇女性専用ホストクラブ〇
〇ハードＳＭ奴隷クラブ〇レズビアン倶楽部〇ホモ・オカマ倶楽部
〇変態痴女と遊ぶ会〇痴漢・覗き趣味の会〇変態同好会・各種
-----------美男・美女会員など多数在籍中-----------
　外部ﾘﾝｸ:www.mttdacomo.jp
-----女性アルバイト随時募集・高収入（日払い）月100万円可能住み込みも可
-----レズビアン・スタッフ●ホモスタッフ●女性専用ホストスタッフ同募-----
外部ﾘﾝｸ:www.mttdacomo.jp

19 ：１３２人目の素数さん：02/08/09 14:55
>>16
いや、明から様に冗談って感じじゃなくて、計算量理論とか知らないと
「ﾌｰﾝ」ですまされそうな所を突いたネタスレだなぁと思ったんよ。

そう思ってスレ開いたらとんでもない事になってた。

20 ：１３２人目の素数さん：02/08/09 15:03
外部ﾘﾝｸ:dempa.2ch.net

396: 02/09/05 23:30 ID:JggUXb/w(5/21)調 AAS
21 ：１３２人目の素数さん：02/08/09 15:04
2からn-1までで順次割ってみればいいんだから、多項式オーダって
あたりまえじゃん、とか思ったが、入力の「桁数」をサイズとして
多項式オーダということだったのですね

22 ：１３２人目の素数さん：02/08/09 15:09
いままで、polynomial timeでdeterministicに解ける方法
がなかったわけですよね？（つい最近習った）
っていうかアメリカはいま大騒ぎです。(Stanfordより)

おまえうざすぎ。
人と話せよ、アフォが。

23 ：１３２人目の素数さん：02/08/09 15:12
>>22
スレの内容が理解できないからって八つ当たりするなよ。

24 ：１３２人目の素数さん：02/08/09 15:15
>>21
順次割っていくにしても√n 以下の数で割れば十分なわけだが。

25 ：１３２人目の素数さん：02/08/09 16:11
>>1のリンク先にあるその論文に雑誌名がないのが気になるが…。

まさか｢論理的｣多項式時間じゃないだろうね？（ｗ

397: 02/09/05 23:30 ID:JggUXb/w(6/21)調 AAS
26 ：１３２人目の素数さん：02/08/09 16:16
2chｽﾚ:newsplus

説明求む

27 ：１３２人目の素数さん：02/08/09 16:20
論文のURL(英語: 数学者の写真あり): 外部ﾘﾝｸ[html]:www.cse.iitk.ac.in
ココにpdfファイルとpsファイルがあるから、取りあえず嫁！

28 ：１３２人目の素数さん：02/08/09 16:33
なんでこんなに静かなんだ・・・

29 ：１３２人目の素数さん：02/08/09 16:45
>>28
このスレの住人が数学オンチだらけだからじゃねーの。
そうじゃなかったら祭りがはじまるはずだよ。

30 ：１３２人目の素数さん：02/08/09 16:49
素因数分解が短時間でできるようになるわけじゃないのか・・・

398: 02/09/05 23:33 ID:JggUXb/w(7/21)調 AAS
31 ：１３２人目の素数さん：02/08/09 16:59
相互リンク　プログラム板

暗号総崩れ-素数判定が多項式時間で可能
2chｽﾚ:tech

32 ：１３２人目の素数さん：02/08/09 17:02
わかりやすく、何かに置き換えてこのすごさを表現してください。
あ、でもこの板の住人達ってそんなにレベル高くなかったんだね。
ゴメンゴメン

33 ：１３２人目の素数さん：02/08/09 17:06
試してみたいんだけど
1 if ( n is of the form a b , b > 1 )
と
12 if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
の ,n の意味が判りません

誰か教えて

34 ：１３２人目の素数さん：02/08/09 17:08
1は「もし nが a^b の形で表現可能なら　素数ではない」　という事だと思うんだけど

35 ：１３２人目の素数さん：02/08/09 17:17
大発見には違いないんだが、「これでRSA崩壊だ！」って
騒いでる奴は一体何なんだ？

399: 02/09/05 23:34 ID:JggUXb/w(8/21)調 AAS
36 ：１３２人目の素数さん：02/08/09 17:19
>>29
論文を読んでるからだと思いたい。

37 ：１３２人目の素数さん：02/08/09 17:26
>>33
ｎは変数。
nが素数かどうかってことでしょ？

38 ：１３２人目の素数さん：02/08/09 17:27
これMATLABだろ？誰かコンパイルしてくれ

39 ：ヽ(´Д｀)ﾉ：02/08/09 17:31
このスレがネタスレかどうかの判定法を教えてくださいです。。。

40 ：１３２人目の素数さん：02/08/09 17:46
>>33
> 12 if( (x-a)^n ≠ (x^n-1) (mod x^r -1 ,n)
> の ,n の意味が判りません

(mod x^r - 1), (mod n) の両方の場合でって意味じゃ。

400: 02/09/05 23:35 ID:JggUXb/w(9/21)調 AAS
41 ：１３２人目の素数さん：02/08/09 17:57
>>28-29
>>36
数学屋にとっては、自分の専門分野以外の大発見なんて
対岸の火事でしかないからだろ。
暗号理論やってるヤツなんてオレの同期には一人だけだし…

42 ：１３２人目の素数さん：02/08/09 18:08
このアルゴリズムが素因数分解に応用できるか
（または与える影響を）検証した人居る？

43 ：１３２人目の素数さん：02/08/09 18:14
>>42
そんな事が簡単に検証できるならとっくにRSA破ってます。

44 ：１３２人目の素数さん：02/08/09 18:15
ランダウ記号でO((log n)^12)と書いているのだが＞外部ﾘﾝｸ[pdf]:www.cse.iitk.ac.in

“多項式時間”とは何を指しているのだろう。

45 ：１３２人目の素数さん：02/08/09 18:21
>>44
n の桁数はO(log n)。多項式時間で解けるつーのは、入力の桁数を
変数とする多項式で実行時間が抑えられるという事。

401: 02/09/05 23:37 ID:JggUXb/w(10/21)調 AAS
46 ：44 ：02/08/09 18:23
>>45
どうもありがとうございました。

47 ：１３２人目の素数さん：02/08/09 18:33
みんな論文読んでるの？　それとも放置？

48 ：１３２人目の素数さん：02/08/09 18:39
>>47
論文読んでとりあえずコード化してみんなでワイワイやってます。
これは面白い…

49 ：41 ：02/08/09 18:40
>>47
専門外だけど、取りあえず読んでます。

50 ：44 ：02/08/09 18:43
>>47
読んでいます。
多くの数学科関係者がチェックしているはず。

402: 02/09/05 23:39 ID:JggUXb/w(11/21)調 AAS
51 ：１３２人目の素数さん：02/08/09 18:44
いままでも確率的な方法で素数判定ができたんだから
そんなに意味ないとおもうんだけど、なにに使えるの？
素因数分解もできる？

52 ：１３２人目の素数さん：02/08/09 18:46
＞いままでも確率的な方法で素数判定ができたんだから
＞そんなに意味ないとおもうんだけど、なにに使えるの？

現時点ではその程度の物って認識で合ってると思う。
後は今後の研究次第かと。

53 ：１３２人目の素数さん：02/08/09 18:48
>>51
応用に関しては、この板よりも他板のほうが詳しいんじゃないかな？

54 ：１３２人目の素数さん：02/08/09 18:52
関連スレ

プログラム
暗号総崩れ-素数判定が多項式時間で可能
2chｽﾚ:tech

ニュース速報＋
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
2chｽﾚ:newsplus

補完よろ。

55 ：１３２人目の素数さん：02/08/09 19:03
ニュー速はかなりもりあがってるね

403: 02/09/05 23:42 ID:JggUXb/w(12/21)調 AAS
56 ：１３２人目の素数さん：02/08/09 19:57
８頁目真ん中の「予想」が気になります。

57 ：１３２人目の素数さん：02/08/09 21:07
素因数分解より素数判定の方が簡単っていうのが信じられない。
馬鹿が理解できるよう、サイモンのように教えて下さい。

58 ：１３２人目の素数さん：02/08/09 21:21
RSAは死んだか？本格的に楕円の時代到来かな

59 ：ネット屋：02/08/09 21:24
ﾎﾟｶｰﾝ（ﾟДﾟ;;

あ、あのさ、これさ・・・・
((( ((（ﾟДﾟ;;)))))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ

60 ：１３２人目の素数さん：02/08/09 21:35
>>57
素因数分解できれば素数かどうか判定はできるから
素数判定は素因数分解より難しくはない。

素数ならばある性質を満たすとわかっていたら、
その性質を満たすかどうか調べるだけで素数でないと判定できる。
だから素数判定の方が素因数分解と同程度の難しさかまたは簡単なはず。

例　nが素数ならば(x-1)^nの1次からn-1次の係数はすべてnで割り切れる。
n=4のとき(x-1)^4=x^4-4x^3+6x^2-4x+1で2次の係数が6で4で割りきれないから
4は素数ではない。

素数でないと判定できても素因数分解する方法はわからないから
まぁ素因数分解の方が難しいのだろう。

404: 02/09/05 23:44 ID:JggUXb/w(13/21)調 AAS
61 ：１３２人目の素数さん：02/08/09 21:35
RSAは素因数分解できないと解読できないっしょ？

62 ：１３２人目の素数さん：02/08/09 21:37
質問。

判定できる素数に何か条件はありますか？
どんな数でも、多項式時間で判定できるの？

63 ：１３２人目の素数さん：02/08/09 21:50
>>62
多項式時間で判定できない数があるとすれば、
素数判定が決定的多項式時間で可能であるとは
言えません。

64 ：１３２人目の素数さん：02/08/09 21:55
下記のスレで議論が活発にされていますので、こちらに移動
しましょう。

2chｽﾚ:newsplus

65 ：１３２人目の素数さん：02/08/09 22:16
>>61
素因数分解をしなくてRSAを解読する方法があるかどうか
はまだ分かっていません。

405: 02/09/05 23:50 ID:JggUXb/w(14/21)調 AAS
66 ：１３２人目の素数さん：02/08/09 23:00
プログラム板2chｽﾚ:tech

＞r=3として例をあげると
＞x^3は1にしてx^4はxにしてx^5はx^2にしてx^6は1にする。
＞x^5 +3x^4 +2x^3 +4x^2 +2x +3 ≡
＞x^2 +3x +2 +4x^2 +2x +3 = 5x^2+5x+5 (mod x^3-1)
＞これならどんな多項式も2次以下の多項式になる。
＞だからいつもr次以下の多項式計算だけですむ。
＞係数の無限長整数変数はr個だけですむ。

これが本質？合ってるのかな
ニュー速読みにくいなぁ…
67 ：１３２人目の素数さん：02/08/09 23:09
>>66 2ページIdentityのProofの次の段落にある
Therefore, to make it feasible we will evaluate both side of (1) modulo a polynomial
of the form x^r-1.
のことでしょう。
暗号総崩れ-素数判定が多項式時間で可能
2chｽﾚ:tech
にも説明してあるよ。

68 ：１３２人目の素数さん：02/08/09 23:32

69 ：１３２人目の素数さん：02/08/09 23:39
桁数nの素数判定をO(n^12)で解くのだな

70 ：１３２人目の素数さん：02/08/10 00:16
このアイディアって、他に応用可能な部分はあるの

406: 02/09/05 23:51 ID:JggUXb/w(15/21)調 AAS
71 ：１３２人目の素数さん：02/08/10 00:26
むちゃくちゃでかい数を多項式時間で素数か判定できるようになった
↓
俺がランダムなむちゃくちゃでかい数をつくって多項式時間で素数か判定する
↓
「あなたの数は素数です」
↓
記録更新
↓
馬

72 ：１３２人目の素数さん：02/08/10 00:27
ＲＳＡてなに？

73 ：１３２人目の素数さん：02/08/10 00:30
日本中央競馬会

74 ：１３２人目の素数さん：02/08/10 00:47
【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明
2chｽﾚ:newsplus
1000レス逝ったのか

75 ：１３２人目の素数さん：02/08/10 00:49
スパコンでもうメルセンヌ素数を計算させてるやつもいるんだろうなぁ。

407: 02/09/05 23:53 ID:JggUXb/w(16/21)調 AAS
76 ：１３２人目の素数さん：02/08/10 00:55
n is of the form a^b
ってどうすりゃい～のさ。これだけで指数時間使ってしまう
教えてくれ～～

77 ：１３２人目の素数さん：02/08/10 00:56
ＲＳＡ亡き後はＥＣＣが台頭か？

78 ：１３２人目の素数さん：02/08/10 00:59
>>76
bを2からlog nまで動かして
nのb乗根を計算して整数になるか判定すれば
O(log^3 n)でできるのでは

79 ：１３２人目の素数さん：02/08/10 00:59
亡くなってないっつの。

80 ：１３２人目の素数さん：02/08/10 01:04
log nを整数精度で浮動小数点を使わないで求める方法キボンヌ

408: 02/09/05 23:55 ID:JggUXb/w(17/21)調 AAS
81 ：１３２人目の素数さん：02/08/10 01:07
>>80
俺なら、範囲を絞った上で、マクローリン展開、かな。

82 ：１３２人目の素数さん：02/08/10 01:13
あきらめた

83 ： ◆Math2chk ：02/08/10 01:20
>>80
２で割っていく。

84 ：１３２人目の素数さん：02/08/10 01:20
完全数たくさん求めてくれ。

85 ：１３２人目の素数さん：02/08/10 01:44
>>80
/* 値は切り捨て、底は整数限定の手抜き版 */
int log_junk(int n, int base)
{
int a ,i;

if (n < 1 || base <= 1) {
exit(-1);
}

for (i = 0, a = 1; a < n; i++, a *= base) {
;
}
return i;
}
と、糞プログラムを書いて手の運動をするテスト

409: 02/09/05 23:56 ID:JggUXb/w(18/21)調 AAS
86 ：１３２人目の素数さん：02/08/10 02:13
>>80
上位ビットから順に1を探す。

87 ：１３２人目の素数さん：02/08/10 02:16
>>86
シフトして上位ビットをキャリーフラグに入れて条件分岐を繰り返す。
シフト回数からlog_2 nがわかる。

88 ：１３２人目の素数さん：02/08/10 02:20
>>87
右シフトして(つまり２で割って)ゼロフラグがたつまで繰り返す。

89 ：１３２人目の素数さん：02/08/10 03:21
すんません。
学のないドシロウトなんですが、
これで一番でっかい素数とかみつかるんですか？

90 ：(o^-')b ：02/08/10 03:36
>>89
ﾊﾞｯﾁﾘ見つかります！(o^-')b　

410: 02/09/05 23:57 ID:JggUXb/w(19/21)調 AAS
91 ：１３２人目の素数さん：02/08/10 03:39
一番でっかい素数って･･････。

92 ：１３２人目の素数さん：02/08/10 04:07
一番でっかい整数が見つけられれば、一番でっかい素数も見つかります。

93 ：１３２人目の素数さん：02/08/10 08:16
プログラム板でコード化が進んでいるようです。
2chｽﾚ:tech

94 ：１３２人目の素数さん：02/08/10 10:30
やっぱり軍とかじゃあ公然の秘密だったのかな。

95 ：１３２人目の素数さん：02/08/10 13:05
ひょっとして2^65536-1が素数かどうかわかるんじゃないか？
たしかまだわかってなかったきがする

411: 02/09/05 23:58 ID:JggUXb/w(20/21)調 AAS
96 ：１３２人目の素数さん：02/08/10 13:11
ああ、違った。
2^n+1
n=2^t
でtが5のとき2^n+1は素数になるが、t>5のとき素数になる場合があるかはわからない
そうです。

97 ：１３２人目の素数さん：02/08/10 15:21
今まで、ネタスレだと思ってたよ（ｗ
すげーな。さすがインド人！年齢関係なんてなくフィールズ賞やって良いん
じゃないの？
暗号全部再構築か…。ネスケもＩＥも今後しばらくの間、怖くてネット通販
使えないかもね。

98 ：１３２人目の素数さん：02/08/10 15:27
＞暗号全部再構築か…。

小一時間問い詰めるぞ。

99 ：１３２人目の素数さん：02/08/10 16:21
なんだか、論文読んでも意外とあっさりしたもんだね。
これで証明できちゃうなんて、拍子抜けしちゃうよ。ハッハ～。

100 ：１３２人目の素数さん：02/08/10 18:57
証明のとこ、わかった？
あのアルゴリズムが有限回で終わるとこと、
素数なら素数と判定される、合成数なら合成数と判定されるというのは
いいんだけど、その後がわからん。

412: 02/09/05 23:59 ID:JggUXb/w(21/21)調 AAS
101 ：　：02/08/10 18:59
>>99
証明の間違いを見つければ神になるチャンス!!!

102 ：１３２人目の素数さん：02/08/10 19:19
外部ﾘﾝｸ:headlines.yahoo.co.jp
>2つの巨大な素数を掛け合わせ、より大きな素数を生み出している
って素数掛け合わせた時点で素数じゃないと思うんだが・・・？

103 ：１３２人目の素数さん：02/08/10 20:17
そこらへんのライターなんて、そんなもん。
サイエンスやコンピュータ関係の専門的な内容は、誤解釈ばっかし。

自分で分かってないのによく書けるな。さすがモノカキのプロだ。

104 ：１３２人目の素数さん：02/08/10 21:10
>>102 ニュー速にスレ立てて馬鹿にしてもｲｲ!!と思うの

105 ：１３２人目の素数さん：02/08/10 21:41
>>102
それの日本語の元記事
ZDNN：暗号技術研究者が素数の問題を克服
外部ﾘﾝｸ[html]:www.zdnet.co.jp
で原文の記事
News: Crypto scientists crack prime problem
外部ﾘﾝｸ[html]:zdnet.com.com

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ

ぬこの手ぬこTOP 0.041s