素数判定は「決定的」多項式時間で可能

素数判定は「決定的」多項式時間で可能 at MATH

1:１３２人目の素数さん
02/08/08 22:24
素数判定は「決定的」多項式時間で可能

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

URLﾘﾝｸ(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つしかレスがないの？
これ、すごいことではないですか？
（数学専門ではないのですが、（コンピュータ専門）
すごい騒ぎになってるのでは？と思ってはじめて
この板に来たのですが）

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
英語が読めません
ばばーい(･∀･)

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日付です。
URLﾘﾝｸ(www.nytimes.com)

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

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

16:１３２人目の素数さん
02/08/09 14:50
っていうか「渋いところ」っていうより、かなり根幹でしょ。

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

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

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

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

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

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

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のリンク先にあるその論文に雑誌名がないのが気になるが…。

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

26:１３２人目の素数さん
02/08/09 16:16
ｽﾚﾘﾝｸ(newsplus板)l50

説明求む

27:１３２人目の素数さん
02/08/09 16:20
論文のURL(英語: 数学者の写真あり): URLﾘﾝｸ(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
素因数分解が短時間でできるようになるわけじゃないのか・・・

31:１３２人目の素数さん
02/08/09 16:59
相互リンク　プログラム板

暗号総崩れ-素数判定が多項式時間で可能
ｽﾚﾘﾝｸ(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崩壊だ！」って
騒いでる奴は一体何なんだ？

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) の両方の場合でって意味じゃ。

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)と書いているのだが＞ URLﾘﾝｸ(www.cse.iitk.ac.in)

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

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

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
読んでいます。
多くの数学科関係者がチェックしているはず。

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
関連スレ

プログラム
暗号総崩れ-素数判定が多項式時間で可能
ｽﾚﾘﾝｸ(tech板)

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

補完よろ。

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

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は素数ではない。

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

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
下記のスレで議論が活発にされていますので、こちらに移動
しましょう。

ｽﾚﾘﾝｸ(newsplus板)

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

66:１３２人目の素数さん
02/08/09 23:00
プログラム板
ｽﾚﾘﾝｸ(tech板:78番)

＞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.
のことでしょう。
暗号総崩れ-素数判定が多項式時間で可能
ｽﾚﾘﾝｸ(tech板:114番)
にも説明してあるよ。

68:１３２人目の素数さん
02/08/09 23:32
>>66
ニュー速+はこれでいいのでは。
ｽﾚﾘﾝｸ(newsplus板:858番)

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

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

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

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

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

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

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

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を整数精度で浮動小数点を使わないで求める方法キボンヌ

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;
}

と、糞プログラムを書いて手の運動をするテスト

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　

91:１３２人目の素数さん
02/08/10 03:39
一番でっかい素数って･･････。

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

93:１３２人目の素数さん
02/08/10 08:16
プログラム板でコード化が進んでいるようです。
ｽﾚﾘﾝｸ(tech板:182番)

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

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

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
証明のとこ、わかった？
あのアルゴリズムが有限回で終わるとこと、
素数なら素数と判定される、合成数なら合成数と判定されるというのは
いいんだけど、その後がわからん。

101:　
02/08/10 18:59
>>99
証明の間違いを見つければ神になるチャンス!!!

102:１３２人目の素数さん
02/08/10 19:19
URLﾘﾝｸ(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：暗号技術研究者が素数の問題を克服
URLﾘﾝｸ(www.zdnet.co.jp)
で原文の記事
News: Crypto scientists crack prime problem
URLﾘﾝｸ(zdnet.com.com)

106:１３２人目の素数さん
02/08/10 21:49
>>102
掛け合わせて1足してるとか、そんなところだろ。

107:名無しゲノムのクローンさん
02/08/10 21:51
>>106
素数と素数を掛け合わせた数は奇数であり、1足すと偶数になるがなにか？

108:１３２人目の素数さん
02/08/10 21:54
>>107
じゃあ、2を足してるとか。
掛け合わせてる以外の計算もあるならあの記事でも良いだろ。

109:名無しゲノムのクローンさん
02/08/10 21:56
>>108
ｱﾌｫか？
素数を求める関数が未だに発見されてないから「素数定理」が長く未解決なんだろ？
お前意味わかってますか？

110:１３２人目の素数さん
02/08/10 22:03
>>106 >>108はどうせニュー速板から来たんだろ。

111:１３２人目の素数さん
02/08/10 22:05
>>106=>>108
おいおい。記事を読んだ上でそんな事を言ってるのか？
RSAの話だぞ。巨大素数を２つ掛け合わせて巨大な
合成数を作るのがRSAの準備段階だろうが。素数判定を
行うってのは掛け合わせる前の２つの素数を選ぶ段階で
使うって意味だ。個の記事書いたライターの方が、1足すだの
2足すだのとトンチンカンな事を言い出さない分お前よりRSAを
理解してんじゃないの？

112:１３２発目の誤爆さん
02/08/10 22:05
■アスキー２４が２ちゃんねるを「総会屋と同じ仕組みの掲示板サイト」と記述

アスキーの記事、削除されちゃいました…

・世論ではなく総会屋? に踊らされた

2ちゃんねるに近いあるインターネット関連会社の社長は、2ちゃんねるの幹部か
ら得た話として証言する。「2ちゃんねるは、運営者や幹部などがそれぞれ別々に会
社を作りカネの流れを見え難くしているが、実際の資金源は複数の大手通信会社系
からの調査費名目のカネ。月額で計約700万円と言い、年間にすれば1億円近く。額
はともあれ、これは通信会社系的には、ぼう大なトラフィックを調査すると言う表
向きの理由が一応は立つ。自社系に都合の悪い書き込みがされた時に優先的に削除
してもらうことも期待している」と前置きし「通信会社系の削除の期待も含めて、2
ちゃんねるは総会屋と同じになっている」と言うのだ。

その具体的な理由として社長は、こう話す。「2ちゃんねるはボランティアの削
除人が書き込みをチェックして、好ましくない書き込みを一所懸命削除している、
ということになっているが、あれはウソ。削除人には給料が支払われ、その給料の
原資となっているのが、まずいことを書き込まれた企業が削除要求とともに渡す裏
金。これはまさに、総会屋の構図そのものだ。これまで裁判になっているのは金額
で折り合えなかったり、裏金を出さない強い態度の企業とだけだ」

もしこの社長の証言が事実だとすれば、警察や検察は、総会屋と同じ仕組みの掲
示板サイトに動かされて摘発したり、異例の動物愛護法による逮捕・起訴や、書類
送検で処理した容疑者を異例の逮捕・起訴に持ち込んだことになる。「社会への影
響」と検察が言う“社会”が、実は総会屋に等しいものだった、とは、警察、検察
にとって何とも情けない話である。

113:１３２人目の素数さん
02/08/10 22:07
>RSA uses two huge prime numbers and multiplies them
>together to produce an even bigger prime.

元記事からして間違ってんのな。

114:１３２人目の素数さん
02/08/10 22:08
第十問題と言って混乱させてみるテスト

115:１３２人目の素数さん
02/08/10 22:12
>>107
２は偶数。

116:１３２人目の素数さん
02/08/10 22:20
>>112

ｽﾚﾘﾝｸ(newsplus板)
URLﾘﾝｸ(ascii24.com)

真偽のほどは定かでない・・・

117:１３２人目の素数さん
02/08/10 22:22
>>115
2が巨大な素数なのか。君の頭の中では。

118:１３２人目の素数さん
02/08/10 22:30
１、２、３、たくさん(ﾌﾟ

119:１３２人目の素数さん
02/08/10 22:46
>>118
いや、３まで数えられたら２が巨大な数だとは思わないだろ（ｗ
>>115の頭の中は「１、・・・えーっと、たくさん！」くらいだと思われ。

120:１３２人目の素数さん
02/08/10 23:16
logの底は何に？

121:１３２人目の素数さん
02/08/10 23:17
>>120
>1の論文の中では底は2だが、
そのことを聞いてるの？

122:１３２人目の素数さん
02/08/10 23:24
>>121
それそれ

123:１３２人目の素数さん
02/08/10 23:59
これって、そこら中の暗号化されたデータが簡単に解読されるようになるってこと？

124:１３２人目の素数さん
02/08/11 00:25
>123
違う。

125:１３２人目の素数さん
02/08/11 01:55
プログラマ板みたいに、「暗号崩壊」とか書いてるわけじゃないのに、
なんでこんなにRSAが崩壊すると勘違いする奴が次から次へと
湧いて出てくるんだ・・・。

126:１３２人目の素数さん
02/08/11 01:55
これって何屋さんの領域なの（数学で）
数論？

127:１３２人目の素数さん
02/08/11 01:57
↑は、スレタイに暗号崩壊とか書いてないのにって事ね。

プログラマ板
暗号総崩れ-素数判定が多項式時間で可能
ｽﾚﾘﾝｸ(tech板)

こういうスレタイなら、勘違いする奴が出てくるのもわかるんだが。

128:１３２人目の素数さん
02/08/11 01:57
>>126
そだね。数論。

129:１３２人目の素数さん
02/08/11 02:05
URLﾘﾝｸ(ntw.e-one.uec.ac.jp)
見つからない罠

130:１３２人目の素数さん
02/08/11 07:32
>>126, >>128
計算量理論、で今回は問題が数論的だった
ではいかが

131:１３２人目の素数さん
02/08/11 07:37
>>127 :
>>1 のリンクで M. Agrawal のページに飛ぶと、
回路計算量とかで錚々たる仕事してるみたい
そっちのコミュニティーのページには載ってるかも

132:あ
02/08/11 08:02
別に素数判定ができるだけで、多項式時間でn=pqが因数分解されるわけでないのに
なんでRSAが崩壊するんかわからん。
確率的手法でも十分だと思うんだけど。

133:１３２人目の素数さん
02/08/11 08:13
>>132
しねーよ。

134:１３２人目の素数さん
02/08/11 08:16
諸君！！！
暗号の問題と関係なく、素数の判定は歴史的にも興味をもたれてきた問題だから
この結果はとても重要であることはいうまでもない。
まず９ページをプリントして、パソコン、携帯電話から離れ、論文を読もうでは
ないか。
我輩もこの書き込みをしたら Shutdown するぞ！

135:１３２人目の素数さん
02/08/11 08:37
>>134
未だに読んでないような奴が何を偉そうに言ってるわけ？
興味のある奴はとっくに読み終えてるんだけど。

136:１３２人目の素数さん
02/08/11 11:33
むしろ、ＲＳＡ暗号がより使いやすくなるって事でファイナルアンサー？
巨大素数が確実に入手できるようになるわけだし。

137:１３２人目の素数さん
02/08/11 14:30
Oはオーダーだけど、
Oの上に~が付いてるのはどういう意味なの？

138:１３２人目の素数さん
02/08/11 15:02
>>137
> We will use the symbol O~(t(n)) for O(t(n)poly(log t(n))), where t(n) is some function of n.

139:１３２人目の素数さん
02/08/11 15:27
>>138
ありがとうございました。
見落としてた…。勝手記法だったのね。

140:１３２人目の素数さん
02/08/11 16:12
>>109 素数定理って、ふつうは、

π(x)
lim ――― = 1
n→∞ x /log x　

だろ？こりはみかいけつだったですか？

141:１３２人目の素数さん
02/08/13 10:35
URLﾘﾝｸ(www.zdnet.co.jp)

正確だけど遅いってさ。
数論な人にとっては証明が正しければそれでOKなのかな？
それとも高速化にも興味あるの？

142:１３２人目の素数さん
02/08/13 13:34
>>141
原理上多項式時間で素数判定ができるかどうかに興味があるんだよ。数論の人は。

143:１３２人目の素数さん
02/08/13 15:12
>>141-142
話が噛み合ってなくないか,君たち?

144:１３２人目の素数さん
02/08/13 18:57
数学板住人だったら「暗号崩壊！？」って誤解よりも
「P≠NP問題解決！？」って誤解をしそうな気がする。

気のせい？

145:１３２人目の素数さん
02/08/13 19:04
けどさ、いくら桁数の多項式時間って言っても
パソコンでやった時に一桁10年かかるようなのだったら
実生活に役立たないよな。

146:１３２人目の素数さん
02/08/13 19:13
たとえ145のような場合でも量子コンピュータのような奴が実用化されなくて、
さらにコンピュータがそれなりに進歩すれば実生活に役立つ。

147:１３２人目の素数さん
02/08/13 23:42
>>145
むしろ、これから「役に立つか」「立たないか」を検証するんじゃないの？

148:１３２人目の素数さん
02/08/14 00:00
他にＰなアルゴリズムを持つかどうか未だにわかっていない問題もたくさんありますが、
その中でこの素数判定というものはどれくらいの難易度にあったのでしょうか。

149:　
02/08/14 02:35
うーん。このことから「拡張されたリーマン予想が真である」
ということは導けないのが残念だね。

150:
02/08/14 03:04

928 ：nanashi ：02/08/13 00:36 ID:*********
ｽﾚﾘﾝｸ(news板)l50
『2chは総会屋？』のやばスレのため、ニュー速板は板ごと夜勤および夜勤の
会社のリーマン削除人により
削除されます。要スレ保存。

929 ：********** ：02/08/13 00:39 ID:********

まーここは夏厨とプロ市民専用らしいから
どんな電波スレ立ててもいいんじゃねーの？

930 ：nanashi ：02/08/13 00:52 ID:********
ｽﾚﾘﾝｸ(accuse板:175-番)
夜勤は夜金＝ウマ＝上場反対＝２ｃｈは金のなる木
URLﾘﾝｸ(jbbs.shitaraba.com)のニュースに多数の大手広告

151:１３２人目の素数さん
02/08/14 06:22
>148

マイケル・ラビンなど，この分野の天才たちが挑戦してきた
歴史的に有名な問題です．もっとも，ＮＰ∩co-NPに含まれることは
自明なので，NP-hardではなかろうと信じられてきました．

ラビンらのアルゴリズムはこれをさらに小さなRPというクラスに
押し下げるものでしたが，リーマン予想云々という条件が
出てきた時点でこれ以上の結果はそう簡単にはでないだろうと
思ってましたので，このニュースには本当にびっくりしました．

いまだにNP-hardnessが未解決な問題として残されているのは
グラフに関する問題が多いです．一番有名なのはグラフ同型問題です．
これなどは，Pに含まれることは絶対にないだろうと思われています．
なぜかというと，もしそれが真ならば，Ｐ＝ＮＰはおろか
無限の多項式階層が有限個につぶれてしまうからです．
ＮＰというクラスはこの階層のもっとも下に位置します．

かれらの論文はまだ未発表ですが，それはおそらく
次のACM STOCに投稿するつもりだからではないでしょうか．
チューリング賞を授与するこの世界で最も権威のある会議ですから．
〆切は12月ぐらいだったと思います．

こんなニュースを聞くと，未解決問題に挑戦したくなりますが
私にはリスクが大きすぎます．人生は有限なので（ｗ

152:　
02/08/14 16:02
グラフ同型問題の良い参考書があったら、おしえてください。
N=NP?に関連する解説が載っていたらなお歓迎です。

153:１３２人目の素数さん
02/08/14 20:43
>>151
手近にある本を調べてもわからなかったので，すみません教えてください．
グラフ同型問題はNP困難かどうかわかってないんですよね？
それでもグラフ同型問題がin PだったらP=NPになっちゃうんですか？
逆にいうと，P=NPになったり多項式階層がつぶれるということは，
グラフ同型問題についてなんらかの意味での困難性が知られてるんでしょうか？

154:151
02/08/14 21:03
>152

学生さんですか？　質問の内容から，これから勉強する人だと思って
答えますね．

グラフに関する研究は，グラフの代数的構造を研究する人と
グラフ問題を解くためのコストを見積もる人に分かれます．
例えばなしをすると，グラフG=(E,V)が与えられたとして，
Gが平面グラフであることの必要十分条件を調べるのが前者で，
Gの平面性を効率的に判定するアルゴリズムを構築するのが後者です．
あなたはPvsNPに興味があるように見受けられましたので，後者の
ための教科書という意味だと受け取りました．

ちなみにグラフの平面性を判定する多項式時間アルゴリズムは
ロバート E．タージャンらによって発見され，かれはこの研究によって
チューリング賞を受賞しました．

さてグラフ理論と（主にPvsNPについての）計算量理論を
バランスよく学ぶための教科書ですが，次の２つをお勧めします．

155:151
02/08/14 21:08
続きです．

１）Computers & Intractability, Michael R. Garey and D. S. Johnson,
W.H. Freeman & Company:
最も有名な教科書です．この本は前半と後半があって，前半は普通の
計算量の教科書です．計算量(PとNP)の基本的な概念はこれでＯＫです．
この本の真価は後半部です．後半はそれまでに知られている膨大な量の
NP-completeな問題のリストと初出の文献リストからなっています．
これらのリストは，いままで見たことのないアルゴリズム上の問題に
突き当たったときにこのリストをながめて似た問題を探すという使い方をします．

２）計算とアルゴリズム，新コンピュータサイエンス講座，浅野孝夫・今井浩，オーム社：
最近出たとてもよい日本語の教科書です．１）で定義を厳密に学んだ後に
よむとよいです．グラフ問題に関係があるのは1章のアルゴリズムの基礎，
7章のグラフアルゴリズム，8章の近似アルゴリズムです．

156:151
02/08/14 21:09
続き２です．

教科書はこの２つで十分です．この2つで訓練すれば
例外的なものを除けばほとんどの論文を自分一人で
読んで，証明の内容をチェックできるようになります．
なおこれ以上の知識をお望みなら，次の２つを参照してください．

３）Computational Complexity, Christos H. Papadimitriou,
Addison Wesley Publishing Company:
様々なクラスの計算量が扱ってあります．ただ書き方が少し特殊なので
まじめに読むとはまります．結果だけ参照すればよいと思います．

４）計算と複雑さ，岩波
うら覚えですが，Algorithms and Complexity Volume A，Elsevier：
という本の和訳だったと思います．2冊組です．古今東西の計算量理論の結果が網羅されてます．
誰も知らないようなことまで載っているので面白いのですが，
とても高いので必要なら研究室で買ってもらってください．

最後に，グラフ同型問題の最新の結果が以下の会議で発表されてます．
Graph Isomorphism is in SPP,
by V. Arvind and Piyush P Kurur，
The 43rd Annual IEEE Symposium on Foundations of Computer Science

157:151
02/08/14 22:04
>153
書きこんでいる間に新しいメッセージがあったようですね．
なんだか前の書きこみと違ってずいぶんご存知のようですが．

え～とすみません．
＞Ｐ＝ＮＰはおろか
これは筆がすべりました．これは下の条件に包含されない可能性がありますね．
＞無限の多項式階層が有限個につぶれてしまうからです．
これは本当です．１）のGarey and Johnsonのリストの最後にある
Open problemの節を見てください．Graph Isomorphismという問題が
出ているはずです．そこのコメントを見てみてください．
参照すべき論文がかいてあるはずです．

それからSamuel R.Buss，Bounded Arithmeticという本に
多項式階層とPvsNPの関係がのってます．

158:１３２人目の素数さん
02/08/14 22:24
153です．どうもありがとうございます．
Garey&Johnson，研究室内で探したんですが見つかりませんでした．
きっとあるはずなので，後日じっくり探して読んでみたいと思います．

159:　
02/08/16 20:52
１００桁とか２００桁、あるいは５００桁程度の整数を素数かどうか
判定するプログラムのソースコードがどこかに落ちていませんか？

160:１３２人目の素数さん
02/08/16 23:57
ZDNNの記事
URLﾘﾝｸ(www.zdnet.co.jp)

161:１３２人目の素数さん
02/08/17 03:32
>>160
テンション的に健全な記事。

162:１３２人目の素数さん
02/08/17 05:37
>>159
UBASICは２７００桁まで扱えるそうだ。
URLﾘﾝｸ(www.rkmath.rikkyo.ac.jp)
どっかに素数判定のプログラムもあるだろう

163:１３２人目の素数さん
02/08/17 06:58
　　　／￣￣￣￣￣￣￣￣
　　　 | 作るのは
　　　＼
　　　　￣∨￣￣￣￣￣￣
　　　　 ∧＿∧
　　　　（ ´Д｀）
　　　／⌒　　⌒ヽ
　　／_／|　　へ＼
　　（ぃ９ ./　　/　＼＼.∧＿∧ ／￣￣￣￣￣￣￣
　　　 /　 ./ 　　　　　ヽ（ ´Д｀）＜君だ！！
　　　（　　/　　　　　　　∪ ,　/　＼＿＿＿＿＿＿＿
　　　＼ .＼＼　　　　 (ぃ９　|
　　　 .＼ .＼＼　　　 /　 /　,、
　　　　　　　 > ））　./　 ∧_二∃
　　　　/ ／／　　./　　￣￣ヽ
　　　 / / /　.＿/ /~￣￣/ ／
　　　/ / / )⌒ ＿ノ　 / ./
　　　（ヽヽ | /　　　（ヽ、
　　　＼__つ).し　　　　＼__つ

164:１３２人目の素数さん
02/08/17 10:04
>159
javaで書けば？

165:．
02/08/17 10:05
注意して下さい！！
　毎日１００以上のスレで大量の荒らし行為を行っている悪質な
　人間が書き込みを行っています。徹底して無視してください。
　皆さん　力を合わせ　一刻も早く２chから追放いたしましょう。
　　　　　　　　　　　　　　　　　　　　２chを守る会

166:１３２人目の素数さん
02/08/17 10:10
100以上のスレってすげーな。

167:１３２人目の素数さん
02/08/26 21:27
age

168:１３２人目の素数さん
02/08/27 03:43
神帝大天才山口人生超教授のおっしゃるところによればP=NPです。
だから素数判定がPなんか自明です。

169:１３２人目の素数さん
02/08/27 07:27
ｲﾝﾄﾞ人もﾋﾞｯｸﾘ

170:１３２人目の素数さん
02/08/27 21:40
>>151
グラフ同型問題が NP完全ならば階層が2段目まで潰れる、
という話なら知ってるけど、P に入っていても潰れると言う話は
あったっけ?

それにしても `Graph Isomorphism is in SPP' は同型問題の
論文例としてはマニアック過ぎると思うのだけど :)

171:151
02/08/28 18:43
>170

>P に入っていても潰れると言う話
これは失礼．NP-completeではなさそうだという予想を
勝手に，多項式では解けなさそうだと脳内変換していたようです．
私データマイニングなんぞやってる似非理論屋なもので．

>それにしても `Graph Isomorphism is in SPP' は
FOCSの会員じゃないので，実はこれ読んでません．
知り合いの専門家にタイトルを教えて意見を聞いたところ
SPP？？？という反応でした．

SPPってはじめて聞いたんですけどどんなクラスなんですかね．

172:１３２人目の素数さん
02/08/31 18:05
>>171
このネタで続けるのもあれだけど、
URLﾘﾝｸ(eccc.uni-trier.de) の TR02-037 見るよろし。
定義はそっからたどりましょう。
FOCS2002 のプログラムももう見られるね。

173:１３２人目の素数さん
02/08/31 19:14
なるほどポキン、新機軸

174:　
02/09/03 22:12
しまった、素数判定に引き込まれて、公募書類と学会発表の申し込みを
出すのを忘れていた。

175:１３２人目の素数さん
02/09/04 10:05

176:１３２人目の素数さん
02/09/05 08:45

177:１３２人目の素数さん
02/09/05 16:10
具体的に素因数分解するのと、素因数の数だけ求めるのには
本質的な時間の違い現れますか？

178:１３２人目の素数さん
02/09/05 22:26
「時間が本質的に違わない」の意味を、
素因数計数問題が易しければ、素因数分解問題も易しい
とするのであれば、本質的に違いはある、と思うに一票

素因数の個数を教えてもらっても、そんなに素因数分解
問題が易しくなった気がしない。
たとえば、RSA とかで使われている
n = p q (p, q: 素数)
は、はじめから素因数の個数が2個とわかっているけど、
効率的に素因数分解せよ、と言われればどうして良いか
わからん。

もちろん、素因数分解問題がそもそも易しいのであれば、
(そうじゃないだろと思ってるが...)両者の時間は
本質的に同じ、ということになるが。

179:１３２人目の素数さん
02/09/05 22:40
>>178
逆だと考えたんだけど。素因数計数問題を解くためには
素因数分解する以外に効率的な手段はないのかなって思った。

180:１３２人目の素数さん
02/09/06 19:45
>>179
例えば試し割りしていく場合、途中で素因数の最大個数は確定すしそうな気がする。

181:　
02/09/08 14:25
桁数の１２乗で、ある予想が成り立てば６乗だというのだけど、
どこまで下げられるのかな。３乗とか４乗ぐらいだとずいぶん
やさしい問題になるんだけど、６乗でも相当、１２乗ならむちゃくちゃ
計算量が必要で、これはつらいね。

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

6 ：１３２人目の素数さん：02/08/09 14:13
だって意味和漢ねーン唾問、俺馬鹿だから。
28 ：１３２人目の素数さん：02/08/09 16:33
なんでこんなに静かなんだ・・・

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

183:１３２人目の素数さん
02/09/08 23:07
>>182
マジレスすると、ニュー速＋に人が流れてたから。

184:１３２人目の素数さん
02/09/08 23:43
マジレスすると、１が、一人で騒いでただけだから

185:１３２人目の素数さん
02/09/08 23:53
>>184
確かに、このスレを盛り上げようとしてたのは>>1を含めても少数だな。
いっそマ板のように「暗号崩壊！？」というデタラメでセンセーショナルな
スレタイにすれば無駄に盛り上がったんだろうな。

186:１３２人目の素数さん
02/09/09 00:11
マジレスすると、自分が分かっちゃうとそれ以上語り合うことないっしょ
数学って
教えるという形以外ではさ
自分の分野に関係していて、進めていけるならともかく、所詮、他ジャンル
という人が多いのだろ

187:１３２人目の素数さん
02/09/09 14:25
そうだね

188:１３２人目の素数さん
02/09/17 10:15
数学板で「盛り上がる」という行為をするネタは大抵電波出現だった気がするんだが。

189:１３２人目の素数さん
02/09/22 06:33
さあ、もうFortranかCで判定プログラムをかけましたか？課題提出の期限は
せまっていますよ。

190:１３２人目の素数さん
02/09/22 09:49
>>1
Ｐ＝ＮＰより確定的多項式時間アルゴリズムは存在します。
　　
　　　参考文献(近刊予定)：御神本　山口人生著

191:１３２人目の素数さん
02/09/24 01:35
12乗がデカイと感じるのはしかたない。
しかしコンピュータの処理速度がいまの10^43倍くらいだったらどうだろう？
指数オーダーに対する12乗オーダーはものすごい脅威になっていたはず。

192:１３２人目の素数さん
02/09/24 05:46
>>191
え？12乗って聞いてまず感じたのは「ちっちゃい」だったんだけど。
冷静に考えてみて初めて実用に向かない程度に大きい事を理解した。

193:１３２人目の素数さん
02/10/08 02:36
人生ちゃんって日本数学会にも顔だしてんの？

194:１３２人目の素数さん
02/10/11 13:19
>190
計算量の授業後に「だれも相手にしてない」と
先生が言っておりました。

195:１３２人目の素数さん
02/10/14 03:09
P=NPあるいはその否定が証明できたら、まちがいなくチューリング賞もの
だし、ある程度若ければフィールズ賞ももらえることはほぼ確実だろう。
ノーベル賞は出ないのも間違いない。

196:１３２人目の素数さん
02/10/14 13:54
ノーベルコンピュータ科学賞もあるべきだ。

197:１３２人目の素数さん
02/10/14 15:02
nobelの時代にコンピュータなんてない

198:１３２人目の素数さん
02/10/14 15:24
ｽﾚﾘﾝｸ(sky板:227番)

199:１３２人目の素数さん
02/10/14 15:28
URLﾘﾝｸ(yahooo.s2.x-beat.com)

200:１３２人目の素数さん
02/10/14 15:33
>>198
ここで止まった。
ｽﾚﾘﾝｸ(eva板:190番)

201:１３２人目の素数さん
02/10/24 03:04
>>196
Turing Prizeもらえばいいじゃん。それともタナカさんみたいに
「今日も同じ服」なんていわれたいの？

202:１３２人目の素数さん
02/10/30 19:22

203:１３２人目の素数さん
02/10/31 14:49
次の大きなニュースもこのスレで出来るかな？

204:１３２人目の素数さん
02/11/23 04:34

205:１３２人目の素数さん
02/12/12 04:19

206: ◆BhMath2chk
03/01/10 07:00
２＾２００３－１＝４００７×６５８８６２２７１４９４６６０９×．．．。

207:山崎渉
03/01/11 12:43
（＾＾）

208:１３２人目の素数さん
03/01/17 04:03
ゲーツあたりがノーベル賞委員会に多額の寄付をすれば、ノーベル計算機賞が
できて、多分第一回目の受賞者は、MS-BASICを作った功績でゲーツが貰う
ことになろうか。

209:１３２人目の素数さん
03/01/23 17:56
（･∀･）ｹﾞﾊﾊﾊﾊ

210:１３２人目の素数さん
03/02/01 01:42
誰かPとNPが真に違うということを証明しようとしている人はいないのか？

211:１３２人目の素数さん
03/02/01 05:36
げーつがMS-BASICを作ったと思ってるんですか？

212:１３２人目の素数さん
03/02/08 18:21

213:１３２人目の素数さん
03/02/16 00:31
P=NPだとすればP(1-N)=0だからP=0またはN=1でなければならない。
すると、一般のPもしくはNについてP＝NPは成り立たない。

214:１３２人目の素数さん
03/02/16 00:35
( ﾟДﾟ)＜ﾅﾅ､ﾅﾝﾄ

215:Quserman ◆KeLXNma5KE
03/02/17 18:56
素数判定が多項式時間で可能だとしても、我々が生きている間に素数判定が終わることの保証がされたわけではない。
それでも、最近の素数判定はめざましい進歩を遂げたと思う。
2^(2^n)+1の形の数は、フェルマーは素数だと思っていたようだが、
オイラーによって、4294967297が素数でないことが示された。
それより大きい数をどうやって素因数分解するのかはよく知らないが、
とにかくコンピュータが無いと殆ど不可能だろう。
その意味では、素数判定が早いとは言えない。
だが、もし素数判定にかかる計算量が、桁数の対数のオーダーになったならどうしよう？
まぁ、私はそんなことはないと信じているが、そんなことになってしまったら、
公開鍵暗号は使えなくなる。
素数関連の問題が人類の運命を左右すると言っても決して過言ではないだろう…。

216:１３２人目の素数さん
03/02/17 19:05
＞公開鍵暗号は使えなくなる。

そうなの？
そもそも公開鍵暗号ってどんな仕組みなの？

217:級数王
03/02/17 20:53
>Quserman
お前は公開鍵暗号のこと全然わかってないね
素数判定が高速で行えれば、暗号の強化にはなるが
暗号を破れるわけじゃない

破るのは素因数分解せんといけんだろ、、、、

218:級数王 ◆Tqj41pFNVk
03/02/17 20:59
＞２１７

　　　　
　　　偽　者　は　消　え　て　く　だ　さ　い　。

219:１３２人目の素数さん
03/02/17 23:06
Manindraさんの講演聴いてきた人いませんかー？

220:１３２人目の素数さん
03/02/19 00:24
２進でb桁の自然数を素因数分解（簡単の為に素因子が２個としてよい）
するために必要な計算量の現在知られている下限は、どのぐらい？

221:１３２人目の素数さん
03/02/19 00:30
下限が strict に押さえられるならみんな苦労していないとおもうが?

222:１３２人目の素数さん
03/02/19 01:53
既出かもしれんがこんなのがあった
URLﾘﾝｸ(www.cybernet.co.jp)
Mapleでの実装。Octaveでも動くかな？

223:222
03/02/19 02:03
OctaveはMatlabモドキだった。フリーのMapleモドキってないのかな。

224:１３２人目の素数さん
03/02/19 02:44
mupad

225:１３２人目の素数さん
03/02/19 02:48
URLﾘﾝｸ(www.tcs.hut.fi)

みれば

C++
Pari/GP
Magma

の実装もあるよ。

次ページ