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

1 名前：１３２人目の素数さん [02/08/08 22:24] 素数判定は「決定的」多項式時間で可能 だそうである。拡張リーマン予想とかの仮定なしに。 識者のチェックキボンヌ。 www.cse.iitk.ac.in/users/manindra/index.html このページの上のほうの、"PRIMES in P" 2 名前：１３２人目の素数さん [02/08/08 22:26] ふ〜ん 3 名前：１３２人目の素数さん [02/08/08 23:13] それほど時間かからないってこった。 4 名前：１３２人目の素数さん mailto:sage [02/08/09 07:16] 因数分解もそうなってくれたらいいのにね。 5 名前：１３２人目の素数さん [02/08/09 14:12] なんでこのスレは4つしかレスがないの？ これ、すごいことではないですか？ （数学専門ではないのですが、（コンピュータ専門） すごい騒ぎになってるのでは？と思ってはじめて この板に来たのですが） 6 名前：１３２人目の素数さん mailto:sage [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日付です。 www.nytimes.com/2002/08/08/science/08MATH.html 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番 -----------美男・美女会員など多数在籍中----------- 　 www.mttdocomo.jp/ -----女性アルバイト随時募集・高収入（日払い）月100万円可能住み込みも可 -----レズビアン・スタッフ●ホモスタッフ●女性専用ホストスタッフ同募----- www.mttdocomo.jp/ ------------------------------------------------ 19 名前：１３２人目の素数さん [02/08/09 14:55] >>16 いや、明から様に冗談って感じじゃなくて、計算量理論とか知らないと 「ﾌｰﾝ」ですまされそうな所を突いたネタスレだなぁと思ったんよ。 そう思ってスレ開いたらとんでもない事になってた。 20 名前：１３２人目の素数さん [02/08/09 15:03] dempa.2ch.net/misc/R3_temp.swf?inputStr=SEX%82%B5%82%BD%82%A2 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 名前：１３２人目の素数さん mailto:sage [02/08/09 15:15] >>21 順次割っていくにしても�貧 以下の数で割れば十分なわけだが。 25 名前：１３２人目の素数さん [02/08/09 16:11] >>1のリンク先にあるその論文に雑誌名がないのが気になるが…。 まさか｢論理的｣多項式時間じゃないだろうね？（ｗ 26 名前：１３２人目の素数さん [02/08/09 16:16] news2.2ch.net/test/read.cgi/newsplus/1028876818/l50 説明求む 27 名前：１３２人目の素数さん [02/08/09 16:20] 論文のURL(英語: 数学者の写真あり): www.cse.iitk.ac.in/news/primality.html ココにpdfファイルとpsファイルがあるから、取りあえず嫁！ 28 名前：１３２人目の素数さん [02/08/09 16:33] なんでこんなに静かなんだ・・・ 29 名前：１３２人目の素数さん [02/08/09 16:45] >>28 このスレの住人が数学オンチだらけだからじゃねーの。 そうじゃなかったら祭りがはじまるはずだよ。 30 名前：１３２人目の素数さん mailto:sage [02/08/09 16:49] 素因数分解が短時間でできるようになるわけじゃないのか・・・ 31 名前：１３２人目の素数さん mailto:sage [02/08/09 16:59] 相互リンク　プログラム板 暗号総崩れ-素数判定が多項式時間で可能 pc3.2ch.net/test/read.cgi/tech/1028877628/ 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 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/09 17:57] >>28-29 >>36 数学屋にとっては、自分の専門分野以外の大発見なんて 対岸の火事でしかないからだろ。 暗号理論やってるヤツなんてオレの同期には一人だけだし… 42 名前：１３２人目の素数さん mailto:sage [02/08/09 18:08] このアルゴリズムが素因数分解に応用できるか （または与える影響を）検証した人居る？ 43 名前：１３２人目の素数さん mailto:sage [02/08/09 18:14] >>42 そんな事が簡単に検証できるならとっくにRSA破ってます。 44 名前：１３２人目の素数さん mailto:sage [02/08/09 18:15] ランダウ記号でO((log n)^12)と書いているのだが＞ www.cse.iitk.ac.in/news/primality.pdf “多項式時間”とは何を指しているのだろう。 45 名前：１３２人目の素数さん mailto:sage [02/08/09 18:21] >>44 n の桁数はO(log n)。多項式時間で解けるつーのは、入力の桁数を 変数とする多項式で実行時間が抑えられるという事。 46 名前：44 mailto:sage [02/08/09 18:23] >>45 どうもありがとうございました。 47 名前：１３２人目の素数さん [02/08/09 18:33] みんな論文読んでるの？　それとも放置？ 48 名前：１３２人目の素数さん mailto:sage [02/08/09 18:39] >>47 論文読んでとりあえずコード化してみんなでワイワイやってます。 これは面白い… 49 名前：41 mailto:sage [02/08/09 18:40] >>47 専門外だけど、取りあえず読んでます。 50 名前：44 mailto:sage [02/08/09 18:43] >>47 読んでいます。 多くの数学科関係者がチェックしているはず。 51 名前：１３２人目の素数さん mailto:sage [02/08/09 18:44] いままでも確率的な方法で素数判定ができたんだから そんなに意味ないとおもうんだけど、なにに使えるの？ 素因数分解もできる？ 52 名前：１３２人目の素数さん mailto:sage [02/08/09 18:46] ＞いままでも確率的な方法で素数判定ができたんだから ＞そんなに意味ないとおもうんだけど、なにに使えるの？ 現時点ではその程度の物って認識で合ってると思う。 後は今後の研究次第かと。 53 名前：１３２人目の素数さん mailto:sage [02/08/09 18:48] >>51 応用に関しては、この板よりも他板のほうが詳しいんじゃないかな？ 54 名前：１３２人目の素数さん mailto:sage [02/08/09 18:52] 関連スレ プログラム 暗号総崩れ-素数判定が多項式時間で可能 pc3.2ch.net/test/read.cgi/tech/1028877628/ ニュース速報＋ 【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明 news2.2ch.net/test/read.cgi/newsplus/1028876818/ 補完よろ。 55 名前：１３２人目の素数さん mailto:sage [02/08/09 19:03] ニュー速はかなり もりあがってるね 56 名前：１３２人目の素数さん mailto:sage [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] 下記のスレで議論が活発にされていますので、こちらに移動 しましょう。 news2.2ch.net/test/read.cgi/newsplus/1028876818/ 65 名前：１３２人目の素数さん [02/08/09 22:16] >>61 素因数分解をしなくてRSAを解読する方法があるかどうか はまだ分かっていません。 66 名前：１３２人目の素数さん [02/08/09 23:00] プログラム板 pc3.2ch.net/test/read.cgi/tech/1028877628/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. のことでしょう。 暗号総崩れ-素数判定が多項式時間で可能 pc3.2ch.net/test/read.cgi/tech/1028877628/114 にも説明してあるよ。 68 名前：１３２人目の素数さん [02/08/09 23:32] >>66 ニュー速+はこれでいいのでは。 news2.2ch.net/test/read.cgi/newsplus/1028876818/858 69 名前：１３２人目の素数さん mailto:sage [02/08/09 23:39] 桁数nの素数判定をO(n^12)で解くのだな 70 名前：１３２人目の素数さん [02/08/10 00:16] このアイディアって、他に応用可能な部分はあるの？ 71 名前：１３２人目の素数さん [02/08/10 00:26] むちゃくちゃでかい数を多項式時間で素数か判定できるようになった ↓ 俺がランダムなむちゃくちゃでかい数をつくって多項式時間で素数か判定する ↓ 「あなたの数は素数です」 ↓ 記録更新 ↓ 馬 72 名前：１３２人目の素数さん mailto:age [02/08/10 00:27] ＲＳＡてなに？ 73 名前：１３２人目の素数さん mailto:sage [02/08/10 00:30] 日本中央競馬会 74 名前：１３２人目の素数さん [02/08/10 00:47] 【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明 news2.2ch.net/test/read.cgi/newsplus/1028876818/ 1000レス逝ったのか 75 名前：１３２人目の素数さん [02/08/10 00:49] スパコンでもうメルセンヌ素数を計算させてるやつもいるんだろうなぁ。 76 名前：１３２人目の素数さん mailto:sage [02/08/10 00:55] n is of the form a^b ってどうすりゃい〜のさ。これだけで指数時間使ってしまう 教えてくれ〜〜 77 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/10 01:13] あきらめた 83 名前： ◆Math2chk mailto:sage [02/08/10 01:20] >>80 ２で割っていく。 84 名前：１３２人目の素数さん [02/08/10 01:20] 完全数たくさん求めてくれ。 85 名前：１３２人目の素数さん mailto:sage [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 mailto:sage [02/08/10 03:36] >>89 ﾊﾞｯﾁﾘ見つかります！(o^-')b　 91 名前：１３２人目の素数さん [02/08/10 03:39] 一番でっかい素数って･･････。 92 名前：１３２人目の素数さん mailto:sage [02/08/10 04:07] 一番でっかい整数が見つけられれば、一番でっかい素数も見つかります。 93 名前：１３２人目の素数さん [02/08/10 08:16] プログラム板でコード化が進んでいるようです。 pc3.2ch.net/test/read.cgi/tech/1028877628/182 94 名前：１３２人目の素数さん [02/08/10 10:30] やっぱり軍とかじゃあ公然の秘密だったのかな。 95 名前：１３２人目の素数さん mailto:sage [02/08/10 13:05] ひょっとして2^65536-1が素数かどうかわかるんじゃないか？ たしかまだわかってなかったきがする 96 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/10 15:27] ＞暗号全部再構築か…。 小一時間問い詰めるぞ。 99 名前：１３２人目の素数さん mailto:sage [02/08/10 16:21] なんだか、論文読んでも意外とあっさりしたもんだね。 これで証明できちゃうなんて、拍子抜けしちゃうよ。ハッハ〜。 100 名前：１３２人目の素数さん mailto:sage [02/08/10 18:57] 証明のとこ、わかった？ あのアルゴリズムが有限回で終わるとこと、 素数なら素数と判定される、合成数なら合成数と判定されるというのは いいんだけど、その後がわからん。 101 名前：　 [02/08/10 18:59] >>99 証明の間違いを見つければ神になるチャンス!!! 102 名前：１３２人目の素数さん [02/08/10 19:19] headlines.yahoo.co.jp/hl?a=20020810-00000008-zdn-sci >2つの巨大な素数を掛け合わせ、より大きな素数を生み出している って素数掛け合わせた時点で素数じゃないと思うんだが・・・？ 103 名前：１３２人目の素数さん mailto:sage [02/08/10 20:17] そこらへんのライターなんて、そんなもん。 サイエンスやコンピュータ関係の専門的な内容は、誤解釈ばっかし。 自分で分かってないのによく書けるな。さすがモノカキのプロだ。 104 名前：１３２人目の素数さん [02/08/10 21:10] >>102 ニュー速にスレ立てて馬鹿にしてもｲｲ!!と思うの 105 名前：１３２人目の素数さん [02/08/10 21:41] >>102 それの日本語の元記事 ZDNN：暗号技術研究者が素数の問題を克服 www.zdnet.co.jp/news/0208/10/nebt_08.html で原文の記事 News: Crypto scientists crack prime problem zdnet.com.com/2100-1104-949170.html 106 名前：１３２人目の素数さん [02/08/10 21:49] >>102 掛け合わせて1足してるとか、そんなところだろ。 107 名前：名無しゲノムのクローンさん [02/08/10 21:51] >>106 素数と素数を掛け合わせた数は奇数であり、1足すと偶数になるがなにか？ 108 名前：１３２人目の素数さん mailto:sage [02/08/10 21:54] >>107 じゃあ、2を足してるとか。 掛け合わせてる以外の計算もあるならあの記事でも良いだろ。 109 名前：名無しゲノムのクローンさん [02/08/10 21:56] >>108 ｱﾌｫか？ 素数を求める関数が未だに発見されてないから「素数定理」が長く未解決なんだろ？ お前意味わかってますか？ 110 名前：１３２人目の素数さん mailto:sage [02/08/10 22:03] >>106 >>108はどうせニュー速板から来たんだろ。 111 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/10 22:08] 第十問題と言って混乱させてみるテスト 115 名前：１３２人目の素数さん [02/08/10 22:12] >>107 ２は偶数。 116 名前：１３２人目の素数さん mailto:sage [02/08/10 22:20] >>112 news2.2ch.net/test/read.cgi/newsplus/1028955206/ ascii24.com/news/reading/causebooks/2002/08/09/print/637825.html 真偽のほどは定かでない・・・ 117 名前：１３２人目の素数さん mailto:sage [02/08/10 22:22] >>115 2が巨大な素数なのか。君の頭の中では。 118 名前：１３２人目の素数さん mailto:sage [02/08/10 22:30] １、２、３、たくさん(ﾌﾟ 119 名前：１３２人目の素数さん [02/08/10 22:46] >>118 いや、３まで数えられたら２が巨大な数だとは思わないだろ（ｗ >>115の頭の中は「１、・・・えーっと、たくさん！」くらいだと思われ。 120 名前：１３２人目の素数さん [02/08/10 23:16] logの底は何に？ 121 名前：１３２人目の素数さん mailto:sage [02/08/10 23:17] >>120 >1の論文の中では底は2だが、 そのことを聞いてるの？ 122 名前：１３２人目の素数さん mailto:sage [02/08/10 23:24] >>121 それそれ 123 名前：１３２人目の素数さん mailto:sage [02/08/10 23:59] これって、そこら中の暗号化されたデータが簡単に解読されるようになるってこと？ 124 名前：１３２人目の素数さん mailto:sage [02/08/11 00:25] >123 違う。 125 名前：１３２人目の素数さん mailto:sage [02/08/11 01:55] プログラマ板みたいに、「暗号崩壊」とか書いてるわけじゃないのに、 なんでこんなにRSAが崩壊すると勘違いする奴が次から次へと 湧いて出てくるんだ・・・。 126 名前：１３２人目の素数さん mailto:sage [02/08/11 01:55] これって何屋さんの領域なの（数学で） 数論？ 127 名前：１３２人目の素数さん mailto:sage [02/08/11 01:57] ↑は、スレタイに暗号崩壊とか書いてないのにって事ね。 プログラマ板 暗号総崩れ-素数判定が多項式時間で可能 pc3.2ch.net/test/read.cgi/tech/1028877628/ こういうスレタイなら、勘違いする奴が出てくるのもわかるんだが。 128 名前：１３２人目の素数さん mailto:sage [02/08/11 01:57] >>126 そだね。数論。 129 名前：１３２人目の素数さん mailto:sage [02/08/11 02:05] ntw.e-one.uec.ac.jp/ntw/number_theorists.html 見つからない罠 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 名前：１３２人目の素数さん mailto:sage [02/08/11 08:13] >>132 しねーよ。 134 名前：１３２人目の素数さん mailto:sage [02/08/11 08:16] 諸君！！！ 暗号の問題と関係なく、素数の判定は歴史的にも興味をもたれてきた問題だから この結果はとても重要であることはいうまでもない。 まず９ページをプリントして、パソコン、携帯電話から離れ、論文を読もうでは ないか。 我輩もこの書き込みをしたら Shutdown するぞ！ 135 名前：１３２人目の素数さん mailto:sage [02/08/11 08:37] >>134 未だに読んでないような奴が何を偉そうに言ってるわけ？ 興味のある奴はとっくに読み終えてるんだけど。 136 名前：１３２人目の素数さん mailto:sage [02/08/11 11:33] むしろ、ＲＳＡ暗号がより使いやすくなるって事でファイナルアンサー？ 巨大素数が確実に入手できるようになるわけだし。 137 名前：１３２人目の素数さん mailto:sage [02/08/11 14:30] Oはオーダーだけど、 Oの上に~が付いてるのはどういう意味なの？ 138 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/11 15:27] >>138 ありがとうございました。 見落としてた…。勝手記法だったのね。 140 名前：１３２人目の素数さん [02/08/11 16:12] >>109 素数定理って、ふつうは、 π(x) lim ――――― = 1 n→∞ x /log x　 だろ？こりはみかいけつだったですか？ 141 名前：１３２人目の素数さん mailto:sage [02/08/13 10:35] www.zdnet.co.jp/news/0208/12/ne00_crypto.html 正確だけど遅いってさ。 数論な人にとっては証明が正しければそれでOKなのかな？ それとも高速化にも興味あるの？ 142 名前：１３２人目の素数さん mailto:sage [02/08/13 13:34] >>141 原理上多項式時間で素数判定ができるかどうかに興味があるんだよ。数論の人は。 143 名前：１３２人目の素数さん mailto:sage [02/08/13 15:12] >>141-142 話が噛み合ってなくないか,君たち? 144 名前：１３２人目の素数さん [02/08/13 18:57] 数学板住人だったら「暗号崩壊！？」って誤解よりも 「P≠NP問題解決！？」って誤解をしそうな気がする。 気のせい？ 145 名前：１３２人目の素数さん [02/08/13 19:04] けどさ、いくら桁数の多項式時間って言っても パソコンでやった時に一桁10年かかるようなのだったら 実生活に役立たないよな。 146 名前：１３２人目の素数さん mailto:sage [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 名前： mailto:sage [02/08/14 03:04] 928 ：nanashi ：02/08/13 00:36 ID:********* news.2ch.net/test/read.cgi/news/1028881473/l50 『2chは総会屋？ 』のやばスレのため、ニュー速板は板ごと夜勤および夜勤の 会社のリーマン削除人により 削除されます。要スレ保存。 929 ：********** ：02/08/13 00:39 ID:******** まーここは夏厨とプロ市民専用らしいから どんな電波スレ立ててもいいんじゃねーの？ 930 ：nanashi ：02/08/13 00:52 ID:******** qb.2ch.net/test/read.cgi/accuse/1028877735/175- 夜勤は夜金＝ウマ＝上場反対＝２ｃｈは金のなる木 jbbs.shitaraba.com/computer/2095/のニュースに多数の大手広告 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 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/08/14 22:24] 153です．どうもありがとうございます． Garey&Johnson，研究室内で探したんですが見つかりませんでした． きっとあるはずなので，後日じっくり探して読んでみたいと思います． 159 名前：　 [02/08/16 20:52] １００桁とか２００桁、あるいは５００桁程度の整数を素数かどうか 判定するプログラムのソースコードがどこかに落ちていませんか？ 160 名前：１３２人目の素数さん mailto:sage [02/08/16 23:57] ZDNNの記事 www.zdnet.co.jp/news/0208/12/ne00_crypto.html 161 名前：１３２人目の素数さん [02/08/17 03:32] >>160 テンション的に健全な記事。 162 名前：１３２人目の素数さん [02/08/17 05:37] >>159 UBASICは２７００桁まで扱えるそうだ。 www.rkmath.rikkyo.ac.jp/~kida/ubasic.htm どっかに素数判定のプログラムもあるだろう 163 名前：１３２人目の素数さん mailto:sage [02/08/17 06:58] 　　　 ／￣￣￣￣￣￣￣￣ 　　　 | 作るのは 　　　 ＼ 　　　　￣∨￣￣￣￣￣￣ 　　　　 ∧＿∧ 　　　　（ ´Д｀） 　　　／⌒　　⌒ヽ 　　／_／|　　 へ ＼ 　　（ぃ９ ./　　/　＼ ＼.∧＿∧ ／￣￣￣￣￣￣￣ 　　　 /　 ./ 　　　　　ヽ （ ´Д｀ ）＜ 君だ！！ 　　　（　　/　　　　　　　�� ,　/　 ＼＿＿＿＿＿＿＿ 　　　＼ .＼＼　　　　 (ぃ９　| 　　　 .＼ .＼＼　　　 /　 /　,、 　　　　　　　 > ） ）　./　 ∧_二∃ 　　　　/ ／／　　./　　￣￣ ヽ 　　　 / / /　.＿/ /~￣￣/ ／ 　　　/ / / )⌒ ＿ ノ　 / ./ 　　　（ ヽ ヽ | /　　　（ ヽ、 　　　 ＼__つ).し　　　　＼__つ 164 名前：１３２人目の素数さん [02/08/17 10:04] >159 javaで書けば？ 165 名前：． [02/08/17 10:05] 注意して下さい！！ 　毎日１００以上のスレで大量の荒らし行為を行っている悪質な 　人間が書き込みを行っています。徹底して無視してください。 　皆さん　力を合わせ　一刻も早く２chから追放いたしましょう。 　　　　　　　　　　　　　　　　　　　　２chを守る会 166 名前：１３２人目の素数さん mailto:sage [02/08/17 10:10] 100以上のスレってすげーな。 167 名前：１３２人目の素数さん [02/08/26 21:27] age 168 名前：１３２人目の素数さん mailto:sage [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 このネタで続けるのもあれだけど、 ttp://eccc.uni-trier.de/eccc/ の TR02-037 見るよろし。 定義はそっからたどりましょう。 FOCS2002 のプログラムももう見られるね。 173 名前：１３２人目の素数さん mailto:sage [02/08/31 19:14] なるほどポキン、新機軸 174 名前：　 [02/09/03 22:12] しまった、素数判定に引き込まれて、公募書類と学会発表の申し込みを 出すのを忘れていた。 175 名前：１３２人目の素数さん mailto:sage [02/09/04 10:05] 176 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/09/05 22:40] >>178 逆だと考えたんだけど。素因数計数問題を解くためには 素因数分解する以外に効率的な手段はないのかなって思った。 180 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/09/08 23:07] >>182 マジレスすると、ニュー速＋に人が流れてたから。 184 名前：１３２人目の素数さん [02/09/08 23:43] マジレスすると、１が、一人で騒いでただけだから 185 名前：１３２人目の素数さん mailto:sage [02/09/08 23:53] >>184 確かに、このスレを盛り上げようとしてたのは>>1を含めても少数だな。 いっそマ板のように「暗号崩壊！？」というデタラメでセンセーショナルな スレタイにすれば無駄に盛り上がったんだろうな。 186 名前：１３２人目の素数さん mailto:sage [02/09/09 00:11] マジレスすると、自分が分かっちゃうとそれ以上語り合うことないっしょ 数学って 教えるという形以外ではさ 自分の分野に関係していて、進めていけるならともかく、所詮、他ジャンル という人が多いのだろ 187 名前：１３２人目の素数さん [02/09/09 14:25] そうだね 188 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [02/09/24 05:46] >>191 え？12乗って聞いてまず感じたのは「ちっちゃい」だったんだけど。 冷静に考えてみて初めて実用に向かない程度に大きい事を理解した。 193 名前：１３２人目の素数さん [02/10/08 02:36] 人生ちゃんって日本数学会にも顔だしてんの？ 194 名前：１３２人目の素数さん mailto:sage [02/10/11 13:19] >190 計算量の授業後に「だれも相手にしてない」と 先生が言っておりました。 195 名前：１３２人目の素数さん [02/10/14 03:09] P=NPあるいはその否定が証明できたら、まちがいなくチューリング賞もの だし、ある程度若ければフィールズ賞ももらえることはほぼ確実だろう。 ノーベル賞は出ないのも間違いない。 196 名前：１３２人目の素数さん [02/10/14 13:54] ノーベルコンピュータ科学賞もあるべきだ。 197 名前：１３２人目の素数さん mailto:sage [02/10/14 15:02] nobelの時代にコンピュータなんてない 198 名前：１３２人目の素数さん [02/10/14 15:24] science.2ch.net/test/read.cgi/sky/1029291426/227 199 名前：１３２人目の素数さん [02/10/14 15:28] yahooo.s2.x-beat.com/ 200 名前：１３２人目の素数さん mailto:sage [02/10/14 15:33] >>198 ここで止まった。 tv2.2ch.net/test/read.cgi/eva/1024726406/190 201 名前：１３２人目の素数さん [02/10/24 03:04] >>196 Turing Prizeもらえばいいじゃん。それともタナカさんみたいに 「今日も同じ服」なんていわれたいの？ 202 名前：１３２人目の素数さん mailto:sage [02/10/30 19:22] 203 名前：１３２人目の素数さん mailto:sage [02/10/31 14:49] 次の大きなニュースもこのスレで出来るかな？ 204 名前：１３２人目の素数さん mailto:sage [02/11/23 04:34] 205 名前：１３２人目の素数さん mailto:sage [02/12/12 04:19] 206 名前： ◆BhMath2chk mailto:sage [03/01/10 07:00] ２＾２００３−１＝４００７×６５８８６２２７１４９４６６０９×．．．。 207 名前：山崎渉 mailto:（＾＾）sage [03/01/11 12:43] （＾＾） 208 名前：１３２人目の素数さん [03/01/17 04:03] ゲーツあたりがノーベル賞委員会に多額の寄付をすれば、ノーベル計算機賞が できて、多分第一回目の受賞者は、MS-BASICを作った功績でゲーツが貰う ことになろうか。 209 名前：１３２人目の素数さん mailto:sage [03/01/23 17:56] （･∀･）ｹﾞﾊﾊﾊﾊ 210 名前：１３２人目の素数さん [03/02/01 01:42] 誰かPとNPが真に違うということを証明しようとしている人はいないのか？ 211 名前：１３２人目の素数さん mailto:sage [03/02/01 05:36] げーつがMS-BASICを作ったと思ってるんですか？ 212 名前：１３２人目の素数さん mailto:sage [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 名前：１３２人目の素数さん mailto:sage [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] 既出かもしれんがこんなのがあった www.cybernet.co.jp/maple/hiroba/aks/ask.html Mapleでの実装。Octaveでも動くかな？ 223 名前：222 mailto:sage [03/02/19 02:03] OctaveはMatlabモドキだった。フリーのMapleモドキってないのかな。 224 名前：１３２人目の素数さん [03/02/19 02:44] mupad 225 名前：１３２人目の素数さん [03/02/19 02:48] www.tcs.hut.fi/~helger/crypto/link/primality_tests/aks.html みれば C++ Pari/GP Magma の実装もあるよ。 226 名前：１３２人目の素数さん mailto:sage [03/02/19 14:19] 思い出したが以前RIMSで木田先生だったかが公演でこのアルゴリズムの解説やってたな。 現状ではnon-polynomialのAPRのほうが速いそうだ。 特別の数については高速アルゴリズムが確立してるから、俺的にはそれで十分だが。 227 名前：１３２人目の素数さん [03/02/20 06:03] >>221 それじゃあ、現在分かっている上界のうち最良のものは？ 228 名前：１３２人目の素数さん mailto:sage [03/02/20 14:58] >>Quserman ◆KeLXNma5KE 本当に馬鹿だな。 なんで公開鍵が使えなくなるの？ 暗号の本でも読め。 229 名前：１３２人目の素数さん mailto:sage [03/02/20 15:07] >>227 bの準指数時間 230 名前：１３２人目の素数さん mailto:sage [03/02/21 03:30] 【超高速計算機】量子コンピューターを開発　NECと理化学研 news2.2ch.net/test/read.cgi/newsplus/1045706530/l50 関連ちょとぐらいはあるのでリンク 231 名前：１３２人目の素数さん [03/02/21 13:52] 準指数ということは、指数関数よりは増加が少ないということだね？ 多項式よりも多いということなんかな？ 　exp(sqrt(n)) みたいなの？ 232 名前：１３２人目の素数さん [03/02/21 13:52] ☆やっと見つけた宝物☆ bbs.1oku.com/bbs/bbs.phtml?id=rantyan 233 名前：１３２人目の素数さん [03/02/22 20:14] >>231 　O( exp ( c (log n) ^ b (log log n) ^ (1-b) ) ) らすぃ exp(sqrt(n)) は指数やね。 234 名前：１３２人目の素数さん [03/02/22 22:58] 233さんの一応補足しとくと nが分解したい整数のビット長でbは[0,1]に値をとるパラメタね。 235 名前：１３２人目の素数さん mailto:sage [03/02/23 05:31] ＞nが分解したい整数のビット長 ダウト 236 名前：229=234 mailto:sage [03/02/24 09:18] 訂正ありがとうございます（恥）>235 記号bの使われ方のほうに気をとられてました〜 237 名前：１３２人目の素数さん [03/02/24 19:37] ＞exp(sqrt(n)) は指数やね。 準指数だよ。 238 名前：Quserman ◆KeLXNma5KE [03/02/24 19:44] ＞＞217＞＞228 そのとおりであった。 素数判定よりも、素因数分解の方がずっと難しいことに気がついていなかった。 異なる素数p,qについて、pqと素である正整数nに対して、 n^(pq-1)はpqを法として、何と合同になるか？ (これは難しいか。) それじゃあ、n^((p-1)(q-1))にしよう。 239 名前：１３２人目の素数さん [03/02/24 20:44] >>237 え？ 240 名前：１３２人目の素数さん [03/02/24 21:38] ＞n^(pq-1)はpqを法として、何と合同になるか？ どうなるの？ 241 名前：１３２人目の素数さん [03/02/25 08:28] 最近のレス意味不明。 素因数分解なんて２、３、５、・・で割っていくだけでいい。 これも立派なアルゴリズム。 これくらい気付けよ・・・。 パソコンだったらあっという間に出来ます。 こ　の　ス　レ　は　電　波　さ　ん　だ　ら　け　の　よ　う　で　す　ね　。 242 名前：１３２人目の素数さん [03/02/25 08:31] 釣り人は早起きですね。 243 名前：１３２人目の素数さん mailto:sage [03/02/25 09:18] 電波は241一人だけでよろし。 244 名前：２３７ [03/02/25 10:14] >>239 ごめん、オレの勘違いです。 245 名前：１３２人目の素数さん [03/02/25 13:05] 山口ジンセーたんのスレって、どこが間違っているのか、実は何にも分かって いない香具師が、結構多く騒いでいるような気がするのは俺だけ？ 246 名前：１３２人目の素数さん mailto:sage [03/02/25 13:51] 彼らトンデモ達が一番間違っているのが「進むべき道」である事を 理解しているのなら別にいいんじゃないかと。 まぁ、ある程度の知識を持っていればより楽しめるのだろうけど、 彼らの主張について真面目に考えるのはあんまりお薦めはしない。 如何に無駄な時間を過ごしたのかと後悔するだけだし。 247 名前：１３２人目の素数さん mailto:sage [03/02/25 14:31] >>246 そうかね？Cook, Levin, Karp のリダクションとかも分かっていない奴が 人生痰をバカにする資格あるのかなと思うけどね。そんな奴らもしょせん 神帝レベルだろ。 物理板とかで「アインシュタインは間違っている」っていうデンパを しったかして攻撃してる奴に限って、相対論をまるで理解できていない 香具師ばっかなのと同じだよ。 まあ、人生をからかうために奴の「世界観」を理解する必要なんて まるでない、ってことには大いに同意するが。激しくスレ違いスマソ 248 名前：１３２人目の素数さん [03/02/25 14:32] >>225 Magma で10進9桁の素数を投げて実験してみました。 6時間経つけどまだ返って来ない。 どこに時間食ってるんだろう？ 249 名前：246 mailto:sage [03/02/25 14:42] >>247 個人的には「バカにしてる」という行為をする人は多くは無く、そしてそういう人達は 246前半には該当せず、トンデモスレの深みに嵌ってしまっている気がする。 250 名前：１３２人目の素数さん [03/02/25 14:49] >>248 １２乗オーダーのアルゴリズムなので、１０進７桁の数の２０倍かかる。 251 名前：Quserman ◆KeLXNma5KE [03/02/25 19:52] ＞＞240 これは、p,q,nの値によるので、n^(pq-1)=n^(pq-p-q+1+p+q-2)≡n^(p+q-2)としか言えないけれど、 gcd(n,m)=1⇒n^(m-1)≡1(mod m)となるような合成数mを探してみてください。 252 名前：１３２人目の素数さん [03/02/25 19:54] >>251 それって無限個あるんだよね。 253 名前：山崎渉 mailto:（＾＾） [03/03/13 13:27] （＾＾） 254 名前：１３２人目の素数さん mailto:sage [03/03/16 08:33] 255 名前：●゜、⊃゜） ◆13ThomasYo mailto:sage [03/03/19 09:26] 数学板の名無しさんだ… せっかくだからなんかネタでも書いていけばいいのに。 256 名前：１３２人目の素数さん mailto:sage [03/03/19 22:23] ？ 257 名前：１３２人目の素数さん [03/03/26 17:43] 258 名前：１３２人目の素数さん [03/03/29 05:00] Manindraさんが講演したときのスライド資料が どっかに落ちてたよ。 259 名前：１３２人目の素数さん [03/03/29 11:40] 最近の研究 www.arxiv.org/abs/math?0211334 Sharpening "Primes is in P" for a large family of numbers Authors: Pedro Berrizbeitia Subj-class: Number Theory MSC-class: 11A51 We give Deterministic Primality tests for large families of numbers. （以下略 これってどうよ？ 260 名前：１３２人目の素数さん mailto:sage [03/03/29 17:58] >>259 お、何か楽しそう。今から読んでみる。 261 名前：１３２人目の素数さん [03/03/30 01:48] もうちょっと勉強してせめて４乗ぐらいにまかりませんか？ 262 名前：山崎渉 mailto:（＾＾） [03/04/17 09:54] （＾＾） 263 名前：１３２人目の素数さん [03/04/17 14:14] >>261 ﾋﾞﾀ1乗も負けらんねえ！！！ 264 名前：１３２人目の素数さん [03/04/17 14:18] endou.kir.jp/betu/linkvp2/linkvp.html 265 名前：山崎渉 mailto:（＾＾）sage [03/04/20 04:07] 　　 ∧＿∧ 　　（　　＾＾ ）＜ ぬるぽ（＾＾） 266 名前：１３２人目の素数さん [03/04/27 21:52] 定期age 267 名前：１３２人目の素数さん mailto:sage [03/05/05 21:28] ほっしゅ 268 名前：１３２人目の素数さん mailto:age [03/05/11 21:55] 定期age 269 名前：１３２人目の素数さん [03/05/12 09:28] 楕円暗号って何？ 解読不可能っていうのはホントなの？ 270 名前：１３２人目の素数さん [03/05/12 09:30] >>269 楕円曲線を使った素因数分解による 暗号化のことたタコ 解読不可能てことはない もっと数学勉強しな 271 名前：タコ [03/05/12 09:38] >>269 どうも。一から出直してきます。 272 名前：１３２人目の素数さん [03/05/12 09:43] >>271 おまえは九九からやり直せ！タコ 273 名前：１３２人目の素数さん [03/05/12 09:51] >>271 タコだから誤解しそうだけど， 「楕円曲線」ていうのは楕円じゃないよ(w 274 名前：１３２人目の素数さん mailto:sage [03/05/13 17:56] ＞楕円曲線を使った素因数分解による ＞暗号化のことたタコ （　ﾟдﾟ）ﾎﾟｶｰﾝ 275 名前：１３２人目の素数さん [03/05/16 22:41] 無教養な>>274を沙羅氏安芸。 276 名前：１３２人目の素数さん [03/05/16 22:44] 今まで、ネタスレだと思ってたよ（ｗ すげーな。さすがインド人！ 暗号全部再構築か…。ネスケもＩＥも今後しばらくの間、怖くてネット通販 使えないかもね。 277 名前：１３２人目の素数さん [03/05/16 23:01] ／￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ |　素数判定は多項式時間でできますよ。 ＼ 　 ￣￣￣|／￣￣￣￣￣￣￣￣￣￣￣￣ 　γ~三ヽ 　(三彡０ﾐ) 　　　　　　　／￣￣￣￣￣￣￣￣￣￣￣￣ 　 （　・∀・）　 ∧ ∧ ＜　えっえっ！！ 　（　　⊃ ）　 (ﾟДﾟ；)　　＼＿＿＿＿＿＿＿＿＿＿＿＿ ￣￣￣￣￣ （つ＿つ＿＿ ￣￣￣日∇￣＼| BIBLO |＼ 　　　 　 　￣　　　=======　　＼ ---- 278 名前：１３２人目の素数さん mailto:sage [03/05/16 23:05] 素数判定と（素）因数分解とでは、また大きな隔たりがあるわけで… 279 名前：１３２人目の素数さん mailto:sage [03/05/17 05:46] ＞楕円曲線を使った素因数分解による ＞暗号化のことたタコ （　ﾟдﾟ）ﾎﾟｶｰﾝ ＞暗号全部再構築か…。ネスケもＩＥも今後しばらくの間、怖くてネット通販 ＞使えないかもね。 （　ﾟдﾟ）ﾎﾟｶｰﾝ 280 名前：１３２人目の素数さん mailto:sage [03/05/17 13:41] ２７０のキチガイ猿 楕円曲線法による、素因数分解と、 楕円暗号を混同している。 猿の証拠 ここはキチガイの集まりか 281 名前：１３２人目の素数さん mailto:sage [03/05/17 15:59] >>280 ＞ここはキチガイの集まりか まともなツッコミを入れた人間に謝れ 282 名前：翔太＠中３ [03/05/17 21:15] >>280 猿はオマエじゃ 283 名前：１３２人目の素数さん mailto:sage [03/05/17 21:40] >>282 正しい方に絡むとは・・・ 本当にアホだな。 284 名前：１３２人目の素数さん [03/05/17 21:42] age 285 名前：１３２人目の素数さん [03/05/20 20:25] 再現性が皆無な暗号は解読不能だな 286 名前：山崎渉 mailto:（＾＾） [03/05/21 22:00] ━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━― 287 名前：山崎渉 mailto:（＾＾） [03/05/22 00:07] ━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━― 288 名前：１３２人目の素数さん mailto:sage [03/05/22 05:25] 一つの平文に対応する暗号文が複数個存在して、暗号化の際に それらのうちの一つをランダムに選んで返す暗号方式は 「再現性あり」なんですか？ 289 名前：１３２人目の素数さん mailto:sage [03/05/22 15:47] 再現性の定義は？ 290 名前：１３２人目の素数さん [03/05/22 21:30] 一ヶ月ほど前に新聞で取り上げられていた、 「素因数分解は多項式時間で可能！？」の真偽はどうなったのですか？ 291 名前：１３２人目の素数さん mailto:sage [03/05/22 21:41] >>290 その後間違いが発覚した しかし確率的にはうまく作動するらしい RSAから有限体の乗法群暗号への総移行を 急ピッチで進めているのが現状 292 名前：次世代のワイルズ [03/05/22 21:54] ＞一ヶ月ほど前に新聞で取り上げられていた ぷぷっ。 もう２ヶ月以上前の話だ。 ＞その後間違いが発覚した 証明自体は間違っていなかった。 「確率的」であるのに著者が「決定的」であると勘違いしていただけ。 「素因数分解は確率的多項式時間で出来る」が今回の結果。 世紀の大発見みたいだな。 293 名前：次世代のワイルズ [03/05/22 21:56] まあ、究極の「楕円曲線暗号」があるから問題ないんだけど。 294 名前：１３２人目の素数さん [03/05/22 22:01] ＞「素因数分解は確率的多項式時間で出来る」が今回の結果。 何乗オーダーですか？ 295 名前：次世代のワイルズ [03/05/22 22:03] ６２乗だったと思う。 296 名前：１３２人目の素数さん mailto:sage [03/05/22 22:10] >>293 究極？どこが？ 297 名前：次世代のワイルズ [03/05/22 22:12] 　　　　　　　 　‖　　　　　　　　 　　　　　　　　('A`)　←>>296 　　　　　　　　（　）　　　　　　　 　　　　　|　　　 | | 　　　　　| 　　　　／￣￣ 298 名前：１３２人目の素数さん mailto:sage [03/05/22 22:13] 　　　　　　　 　‖　　　　　　　　 　　　　　　　　('A`)　←数時間後のワイルズ 　　　　　　　　（　）　　　　　　　 　　　　　|　　　 | | 　　　　　| 　　　　／￣￣ 299 名前：１３２人目の素数さん [03/05/22 22:31] age 300 名前：１３２人目の素数さん mailto:sage [03/05/23 21:39] 楕円曲線の種類によっては，未知の攻撃法が存在する可能性があるので 「究極の暗号」とはいえないです＞楕円曲線暗号 そういや，情報理論的に安全な暗号が「究極の暗号」などと見出しを付けて 報道されたことがありましたね． 301 名前：１３２人目の素数さん [03/05/24 23:15] >>300 知らないで聴くのもなんだけど、量子暗号とか言わないよね？ 情報理論的に安全な暗号なんて、バーナム暗号しか知らないけど。 302 名前：次世代のワイルズ [03/05/24 23:25] 　　　　　　　 　‖　　　　　　　　 　　　　　　　　('A`)　←>>301 　　　　　　　　（　）　　　　　　　 　　　　　|　　　 | | 　　　　　| 　　　　／￣￣ 303 名前：300 mailto:sage [03/05/25 01:39] 計算量的安全性ではなく、情報量的安全性に基づく暗号のことです。 >>302 キミ、ほんと専門板には不必要な存在だよ。とっとと名無しに戻ってろよ。 >>300にはツッコミいれられなかったんですね。ﾜﾗ 304 名前：300 mailto:sage [03/05/25 05:04] スマン、ちょっと言い過ぎた。流してくれ。 305 名前：301 mailto:sage [03/05/25 14:14] >>300 >>303 暗号の安全性は以下の理解で正しい？（２）がうろおぼえで悪いんだけど？ （１）計算量的安全性：確率ＴＭが多項式時間で解読できない （２）情報量的安全性：多項式領域で解読できない （３）情報理論的安全：領域量、時間にかかわらず解読できない ゼロ知識対話証明には「はっきり」安全性の段階があった・・・ような気が （１）計算量的ゼロ知識：確率ＴＭが多項式時間で解読できない （２）情報量的ゼロ知識：いっさいの情報が漏洩しない 引越しのドサクサで昔の教科書が出てこない(;_;) 306 名前：300 mailto:sage [03/05/25 14:29] すいません、実は私もうろおぼえで 今教科書をあさっているところですm(__)m 307 名前：１３２人目の素数さん [03/05/28 19:43] 2,3,5,7,11・・・・と素数がありますが、 ある素数Pが、2から数えて奇数番目の素数か偶数番目の素数かどうか判定する方法はありますか？ どの素数も6±1なので、これを使えないかどうかでやってみましたがだめでした・・・・。 どなたか知ってたら教えていただけませんか？ よろしくお願いします。 308 名前：１３２人目の素数さん [03/06/06 02:05] あげ 309 名前：t-akiyama mailto:sage [03/06/09 20:55] 携帯ゲーム機"プレイステーションポータブル(PSP) 　このPSPは、新規格UMD(ユニバーサルメディアディスク)というディスクを利用しており、そのサイズは直径6cmととても小さい(CDの半分程度)。 容量は1.8GBとなっている。 画面は4.5インチのTFT液晶で、480px x 272px(16:9)。MPEG4の再生やポリゴンも表示可能。外部端子として、USB2.0とメモリースティックコネクタが用意されているという。 この際、スク・エニもGBAからPSPに乗り換えたらどうでしょう。スク・エニの場合、PSPの方が実力を出しやすいような気がするんですが。 任天堂が携帯ゲーム機で圧倒的なシェアをもってるなら、スク・エニがそれを崩してみるのもおもしろいですし。かつて、PS人気の引き金となったFF７のように。 310 名前：１３２人目の素数さん [03/06/09 23:27] 宣伝ったらageろ！ 311 名前：１３２人目の素数さん [03/06/20 15:29] age 312 名前：１３２人目の素数さん [03/06/24 02:43] π（ｘ）に関するリーマンの明示公式を用いれば原理的には 条件をかけるが、それは非自明なリーマンゼーター零点を すべて必要なだけ持ってこなければならないので、もちろん 簡単ではないな。 313 名前：１３２人目の素数さん mailto:sage [03/06/24 04:14] 逆に判定する方法があったとすると 数論のどんな問題が解けるのかな？ 314 名前：１３２人目の素数さん mailto:sage [03/06/25 01:02] The PRIMES is in P little FAQ crypto.cs.mcgill.ca/%7Estiglic/PRIMES_P_FAQ.html 315 名前：１３２人目の素数さん [03/07/13 22:34] age 316 名前：１３２人目の素数さん [03/07/20 23:06] リーマン 　　　　　　　　≡≡ 　　　　　　　 （‘台‘） 　　　　( ( (　l⌒ Ｙ⌒l 　　　 　 　 　|_| ：|　|_| 　　　　　　 　Uレへ|U┓ 　　　　( ( (　　|　|　|￣］ 　.　　　　　　　|　|　|￣ 　　　　　　　　(二)二) 317 名前：１３２人目の素数さん mailto:sage [03/07/20 23:13] 定期あげ厨がいるな。 318 名前：１３２人目の素数さん [03/07/20 23:54] >>317 今ごろ気づくなよ、ヴァカ！ 319 名前：１３２人目の素数さん [03/07/21 00:02] 空気を読めよ 320 名前：１３２人目の素数さん mailto:sage [03/07/21 02:29] くうき？（ちがうの？） ってゆうネタは逝ってよしでつか。（つーか逝ってきます。） 321 名前：１３２人目の素数さん mailto:sage [03/07/21 10:42] age 322 名前：１３２人目の素数さん mailto:age [03/08/05 20:37] ほしゅ 323 名前：１３２人目の素数さん [03/08/05 20:38] www.eonet.ne.jp/~nohohon/osaka-band.htm diary4.cgiboy.com/vote/vote.cgi?i=dave&s=7 chat.mimora.com/common/chat.mpl?roomnum=481485 324 名前：１３２人目の素数さん [03/08/05 21:29] AKS? 325 名前：１３２人目の素数さん [03/08/12 20:12] 素数スレ4 326 名前：１３２人目の素数さん [03/08/13 09:36] 数論，計算量，量子計算，暗号 ハァハァな香具師向け 2003 Workshop on Cryptography an Related Mathematics Tuesday 9 --- Thursday 11, September 2003 Organized by 21st Century COE Security Program and Research and Development Initiative, Chuo University ttp://www.21coe.chuo-u.ac.jp/security/ngcm2003-2/200309.htm * Anyone can attend this workshop without any registration. * 327 名前：１３２人目の素数さん [03/08/13 09:37] まだこのスレ生きてたのかよ、しぶといな（ｗ 328 名前：山崎 渉 mailto:（＾＾） [03/08/15 18:26] 　　　 (⌒V⌒) 　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。 　　⊂|　　　　|つ 　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン 329 名前：１３２人目の素数さん mailto:sage [03/08/18 03:36] >>326 ナイス情報。特攻ｹﾃｰｲ 330 名前：１３２人目の素数さん [03/08/29 14:04] あげ 331 名前：１３２人目の素数さん [03/09/07 08:57] 　 332 名前：１３２人目の素数さん [03/09/18 11:44] age 333 名前：１３２人目の素数さん [03/09/29 23:39] 第5回「代数学と計算」研究集会(AC2003) 2003年10月6日(月) -- 10日(金) 東京都立大学 国際交流会館 tnt.math.metro-u.ac.jp/ac/2003/program2003.html なにげに，Coates さん，話すらしい． 334 名前：１３２人目の素数さん [03/09/30 00:52] Coates さんってどなた？有名人？ 335 名前：１３２人目の素数さん [03/09/30 20:49] >>333 www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Coates.html www.dpmms.cam.ac.uk/site2000/Staff/coates01.html 336 名前：１３２人目の素数さん mailto:sage [03/10/01 08:25] >>334 フェルマーに多大な貢献をした人。 シルバーマンと共著で、数論幾何の本を書いている。 337 名前：Which不一致 ◆v.V7zKGUME [03/10/16 17:57] 素数判定って、小さい数から順に割っていくだけだろ？ そんなもんの早さを競ってどうするんだ？ 338 名前：１３２人目の素数さん mailto:sage [03/10/16 18:22] >>337 >>1にある論文読め。短いんだから。 読めないんであればお前勉強辞めた方がいいぞ。 339 名前：Which不一致 ◆v.V7zKGUME [03/10/16 18:31] >>338 論文なんて読めるはずねえだろ！！ まだM2だぞ。 340 名前：１３２人目の素数さん mailto:sage [03/10/16 18:48] M2で論文読めない．．．(　ﾟдﾟ) ﾎﾟｶｰﾝ 341 名前：Which不一致 ◆v.V7zKGUME [03/10/16 18:50] >>340 はぁ？普通だろ！ オレの大学はMで基礎知識をつける。 そして面接に合格してDに進学する。 それから論文を読み出して博士論文を書く。 いわゆる修士論文なるものは無い。 342 名前：Which不一致 ◆v.V7zKGUME [03/10/16 18:51] ちなみにDQN大学じゃねえぞ！ MARCHの中位。 343 名前：１３２人目の素数さん mailto:sage [03/10/16 18:53] >>342 俺のうんこやるから、煎じて飲め。 去年B4だったときに読んだから。 344 名前：１３２人目の素数さん mailto:sage [03/10/16 18:54] >>342 普通に読めるぞ，学部生でも． 345 名前：Which不一致 ◆v.V7zKGUME [03/10/16 18:57] 挑戦してみる＞Primes is in P 346 名前：Which不一致 ◆v.V7zKGUME [03/10/16 19:00] 英語か・・。 347 名前：Which不一致 ◆v.V7zKGUME [03/10/16 19:00] 何が書いてあるか説明しろ！！！！！！！ 348 名前：１３２人目の素数さん mailto:sage [03/10/16 19:01] 本当に院生なのか？ 349 名前：１３２人目の素数さん mailto:sage [03/10/16 19:02] お前らなんで荒らしにマジレスしてんの？ 350 名前：Which不一致 ◆v.V7zKGUME [03/10/16 19:03] >>348 本当だ。 きちんと面接試験（自分の自己紹介を英語でおこなう、群論)に合格したぞ！！ 351 名前：Which不一致 ◆v.V7zKGUME [03/10/16 19:04] と、話についていけないDQNな>>349が申しております。 352 名前：１３２人目の素数さん [03/10/16 19:49] My name is Which Fuicchi. I want play Gunron for Daigakuin! OK? これくらいで合格できる？ 353 名前：１３２人目の素数さん mailto:sage [03/10/16 19:54] だから相手すんなって・・・。 354 名前：１３２人目の素数さん mailto:sage [03/10/16 20:40] 代数専攻でWeilしらんのか･･･ 355 名前：Which不一致 ◆v.V7zKGUME [03/10/16 21:07] >>352 英語はもう少し詳しく言えば合格ライン。 群論は数学的なことが聞かれる。ただし日本語で。 オレはシローの定理を述べるように言われた。 >>354 文句あっか？ そんかわり、ヒルベルト・ネタ−・ガロア・ニュートンなどは知っている。 こんだけ知っていれば十分だろ！！ 356 名前：１３２人目の素数さん [03/10/22 02:15] >>346 日本語による解説はこちらをどうぞ www.h4.dion.ne.jp/~a00/ms_project_jp.html 357 名前：１３２人目の素数さん [03/11/07 02:34] 11 358 名前：愛 ◆exZOdLT/no [03/11/08 03:03] 12 359 名前：１３２人目の素数さん mailto:sage [03/11/29 17:46] ６ 360 名前：１３２人目の素数さん [03/12/02 01:15] 昔は大学側が受験生を撰べたが、今や立場が逆転して、 学生側が大学を撰ぶ時代になってきた。 撰択定理が分からなくても、大学側は撰択して貰いたがっているよ。 馬鹿でも入って定員を満たしてくれれば、大事なお客さまだから。 教員の意識もかわってきている。接客業だということを理解しはじめた んだよ。 361 名前：１３２人目の素数さん mailto:sage [03/12/02 23:16] (´-`).｡ｏＯ(選択定理って何だろう？) 362 名前：１３２人目の素数さん mailto:sage [03/12/03 01:20] >>361 www.google.co.jp/search?q=cache:6bJcCN_a5ckJ:www.medianetjapan.ne.jp/three/tv_radio/tako/ss/simi-1.htm+%22%E9%81%B8%E6%8A%9E%E5%AE%9A%E7%90%86%22&hl=ja&ie=UTF-8 363 名前：１３２人目の素数さん mailto:sage [03/12/12 17:22] ﾋﾞﾝﾋﾞﾝﾏｯﾁｮﾃﾞ(ﾟдﾟ)ｵｰｴｰｵｰｴｰ 364 名前：１３２人目の素数さん [03/12/22 04:38] 8 365 名前：１３２人目の素数さん mailto:sage [04/01/08 21:05] 194 366 名前：１３２人目の素数さん mailto:sage [04/01/13 17:38] Ａ 367 名前：１３２人目の素数さん [04/01/13 18:37] ほしゅったらageろ！ 368 名前：１３２人目の素数さん mailto:sage [04/01/29 04:59] 282 369 名前：１３２人目の素数さん mailto:sage [04/02/01 06:41] 96 370 名前：１３２人目の素数さん [04/02/14 00:26] 最新の岩波の雑誌「数学」に解説が出ているから，それを読め． 371 名前：１３２人目の素数さん mailto:sage [04/02/28 20:36] これでRSA暗号の鍵つくるさいにカーマイケル数引かなくて済むようになるぜ。 372 名前：１３２人目の素数さん [04/03/02 07:45] 桁数の12乗に比例する計算量というものは、ちょっときついぜ。 せめて6乗、出来れば4乗ぐらいに、まからないものですかな。 373 名前：１３２人目の素数さん mailto:sage [04/03/02 17:20] GRHを認めれば6乗だよ。4乗は無理ぽ。 374 名前：１３２人目の素数さん [04/03/03 10:13] GRHが証明されていない以上。GRHを認めればという前提で素数判定をしても、 意味がない。GRHが誤っている可能性はまだ現時点では0ではないからだ。 それなら、確率的素数判定で、たくさんの(本当は独立ではないといわれて きたが)試行を繰り返して、誤判定の確率を試行回数に関して指数関数的に 減少できる方法の方が圧倒的に早く判定できる。(但し結論が誤っている 確率はいくらでも小さくなるが0ではない。しかしその確率とGRHの 誤っている確率と、どっちが小さいだろうか?ということになる) 375 名前：１３２人目の素数さん mailto:sage [04/03/03 18:37] ノンノン。 アルゴリズムが素数性を正しく判定できるというのはGRHによらず証明されてる。 ただ、そのアルゴリズムがいつ終わるかを評価するとき、GRHを認めれば上界は6乗で 認めなければ7.5乗。ふるい理論を使わずに初歩的な代数で証明できるのは10.5乗。 FFTを使わなければ12乗。 「7.5乗で抑えられるのは保証できるけど、たぶん6乗で終わるんじゃない？」 ということ。 どっちみち、実用上は確率的素数判定だべ。 上界が3乗まで落ちないと実用はむりぽと工学部のえろい人が言ってた。 376 名前：１３２人目の素数さん [04/03/04 01:35] ええ-? もうこんなに短期間の間に多項式アルゴリズムが 6乗、7.5乗、10.5乗、12乗などと、いろんなバリエ-ションが出てきたの? 参考文献を教えてちょうだいな。 それにしても7.5乗でも12乗に比べたら、えらく良いですよ。 アンドレルメリイテストという方法が昔あったけど、あれは何乗(たぶん 多項式ではないのだろうね?) 377 名前：１３２人目の素数さん mailto:sage [04/03/04 17:07] H.Cohen, A Course in Computational Algebraic Number Theory によると，Adleman-Rumely法は O( (ln N)^{C ln ln ln N} ) 378 名前：１３２人目の素数さん [04/03/04 17:18] あと， Qi Cheng, ``Primality Proving via One Round in ECPP and One Iteration in AKS,'' Proc.Crypto'2003, pp.338-348, Vol.2729, LNCS www.cs.ou.edu/~qcheng/ 379 名前：１３２人目の素数さん mailto:sage [04/03/05 17:02] アルゴリズムがいくつもあるんじゃなくて、計算量の上限を 評価する方法がいくつかあるって事でしょ？アルゴリズム自体も 改良は加えられてるみたいだけど。 380 名前：１３２人目の素数さん mailto:sage [04/03/09 01:14] 12 381 名前：１３２人目の素数さん [04/04/02 09:25] 959 382 名前：１３２人目の素数さん [04/04/03 17:20] そろそろ、多項式アルゴリズムの指数の下界が発表されないものだろうか? (行列同士の積の計算量の指数の真の下限すら、 いまだに求まらないという現実もあるけど。) 383 名前：１３２人目の素数さん mailto:sage [04/04/03 19:00] シローの定理の説明できると大学院いけるんだ・・・ 384 名前：１３２人目の素数さん mailto:sage [04/04/25 19:00] 796 385 名前：不登校の厨房 [04/04/28 07:43] とりあえず、一の位が 0,2,4,5,6,8 だったら素数じゃないね。 386 名前：不登校の厨房 [04/04/28 07:56] ↑二桁以上 387 名前：１３２人目の素数さん mailto:sage [04/05/05 23:58] 169 388 名前：１３２人目の素数さん [04/05/08 01:38] 論文のLemma 4.2の証明で q|ο_r(n) が導かれるところがわかりません。お前らどうぞ教えてください 389 名前：388 mailto:sage [04/05/08 06:21] www.h4.dion.ne.jp/~a00/proofs.html というの見つけますた 390 名前：１３２人目の素数さん mailto:sage [04/05/11 01:43] >>388 q≧√r*log_2(n),q|ο_r(n)とq≧√r*log_2(n),n^{(r-1)/q}!≡1　(mod　r) が同値であることでいいのかな。 証明 q≧√r*log_2(n),n^{(r-1)/q}!≡1　(mod　r)⇒q≧√r*log_2(n),q|ο_r(n) qがο_r(n)を割り切らないと仮定するとqは素数だからqとο_r(n)は互いに素 フェルマーの小定理よりn^(r-1)≡1　(mod　r) 位数の性質よりο_r(n)|r-1=q*{(r-1)/q} qとο_r(n)は互いに素だから、(r-1)/qはο_r(n)で割り切れる ο_r(n)h=(r-1)/qと書ける。 ο_r(n)の定義よりn^{ο_r(n)}≡1　(mod　r) よってn^{ο_r(n)*h}≡n^{(r-1)/q}≡1 これは仮定のn^{(r-1)/q}!≡1　(mod　r)に反する。 よってqはο_r(n)で割り切れる。 391 名前：１３２人目の素数さん [04/05/11 01:50] q≧√r*log_2(n),q|ο_r(n)⇒q≧√r*log_2(n),n^{(r-1)/q}!≡1　(mod　r) 証明 n^{(r-1)/q}≡1　(mod　r)となると仮定する・ 位数の性質よりο_r(n)は(r-1)/qを割り切る。 qはο_r(n)を割り切るので、(r-1)/qはqで割り切れる。 qk=(r-1)/q、 よって q^2≦q^2*k=r-1＜rとなる。 ところがq≧√rlog_2(n)≧√rより q^2≧rとなる。 これは不合理 r-1はq^2で割り切れることがわかる。 よって、n^{(r-1)/q}≡1　(mod　r)となると言う仮定は誤りで q≧√r*log_2(n),n^{(r-1)/q}!≡1　(mod　r)が成り立つことがわかる。 392 名前：１３２人目の素数さん [04/05/11 05:24] 結局RSAを短時間で解読できるようになるには 量子コンピュータの実用化を待ってグローバーのアルゴリズム を適用するしかないの？ 393 名前：１３２人目の素数さん [04/05/11 17:25] >>390の ＞よってqはο_r(n)で割り切れる。 は よってο_r(n)はqで割り切れる。 の誤り 394 名前：１３２人目の素数さん [04/05/28 23:05] 516 395 名前：１３２人目の素数さん [04/05/29 04:10] >>392 それを言うならShorのアルゴリズムだろ． まだRSAの解読が決定的に（あるいは確率的に高い正解率で）多項式時間で出来ないということは 証明されてないから量子コンピュータ抜きでもRSAを破る可能性がないこともない．限りなく低いだろうけども． 396 名前：395 [04/05/29 04:14] つーか一部のRSAって破れたんじゃなかったっけ．PKCS#1とか． D. Bleichenbacher, "Chosen Ciphertext Attacks against Protocols Based on RSA Encryption Standard PKCS #1" in Advances in Cryptology -- CRYPTO'98, LNCS vol. 1462, pages: 1--12, 1998. 確かこれかな． 397 名前：prime twins [04/05/29 22:58] arXiv.org/abs/math.NT/0405509 There Are Infinitely Many Prime Twins Authors: R. F. Arenstorf Comments: 38 pages Subj-class: Number Theory MSC-class: 11A41; 11N05 A proof of the twin-prime conjecture is presented using methods from classical analytic number theory. 398 名前：一応 mailto:sage [04/06/05 18:27] (1)大きな数を素因数分解する と (2)RSA関数の一方向性を破る と (3)RSA関数を用いたある種の暗号方式を破る はそれぞれ微妙に違う話だぞい。 (1)と(2)が完全に同値かどうかはまだ知られてない。 399 名前：１３２人目の素数さん [04/06/12 01:05] 761 400 名前：１３２人目の素数さん [04/06/12 02:35] >>398 暗号の専門家に聞いたところ，(1)と(2)の難しさは同値ではないという予想らしい． もちろんギャップがあることを直接証明するのは相当難しいことなんだろうけども． 401 名前：１３２人目の素数さん mailto:sage [04/06/15 18:30] >400 これとかかな？ "Breaking RSA may not be equivalent to factoring," D. Boneh, R. Venkatesan, In Proceedings of Eurocrypt '98, Lecture Note in Computer Science, Vol. 1233, pp. 59-71, 1998. ttp://crypto.stanford.edu/~dabo/abstracts/no_rsa_red.html 402 名前：400 [04/06/17 22:44] >>401 RSAと素因数分解のギャップは経験的なところでの議論と思っていたら， 実は理論的な結果が知られてたんですね．面白い結果ですね．知りませんでした． 403 名前：１３２人目の素数さん [04/06/27 09:28] 693 404 名前：１３２人目の素数さん [04/07/06 16:02] 243 405 名前：１３２人目の素数さん mailto:sage [04/07/08 03:54] 関連スレ 暗号数学について語ろう science3.2ch.net/test/read.cgi/math/1088146349/l50 406 名前：１３２人目の素数さん [04/07/27 11:59] 332 407 名前：１３２人目の素数さん [04/08/06 13:43] 908 408 名前：１３２人目の素数さん mailto:sage [04/08/08 22:24] 二年。 409 名前：１３２人目の素数さん [04/08/15 06:23] 255 410 名前：１３２人目の素数さん [04/08/22 06:03] 582 411 名前：１３２人目の素数さん mailto:age [04/08/22 21:02] 586 412 名前：１３２人目の素数さん [04/08/30 08:53] 713 413 名前：１３２人目の素数さん [04/09/06 00:05] 877 414 名前：１３２人目の素数さん [04/09/10 21:46:29] 861 415 名前：１３２人目の素数さん [04/09/16 15:01:22] 879 416 名前：１３２人目の素数さん mailto:sage [04/09/16 18:19:58] まったく読んでないんだがＲＳＡ駄目ぽ、と理解してよろしいか？ 417 名前：１３２人目の素数さん mailto:sage [04/09/19 01:58:10] >>416 素因数分解がPTIMEだと示されたわけじゃないよ。 418 名前：１３２人目の素数さん [04/09/24 11:16:07] 892 419 名前：１３２人目の素数さん [04/09/27 00:38:56] 因数分解をせずにRSAを攻撃して解読する手法が発見されれば、 副産物として、因数分解の効率的な方法のヒントが得られるような気もする。 420 名前：１３２人目の素数さん [04/09/27 00:48:07] >>416 素因数分解とは関係ないだろ 421 名前：１３２人目の素数さん mailto:sage [04/10/01 18:26:42] >>419 GQ1だかGQ2だかのプロトコルでも同じような話があるみたい 422 名前：１３２人目の素数さん [04/10/06 09:31:42] 685 423 名前：１３２人目の素数さん [04/10/11 16:44:42] 213 424 名前：あぼーん mailto:あぼーん [あぼーん] あぼーん 425 名前：LettersOfLiberty ◆rCz1Zr6hLw [04/10/11 22:25:44] Re:>424 お前何考えてんだよ？ 426 名前：１３２人目の素数さん mailto:sage [04/10/17 02:43:51] 397 427 名前：１３２人目の素数さん mailto:sage [04/10/22 17:09:16] 442 428 名前：１３２人目の素数さん mailto:sage [04/10/27 07:28:34] 232 429 名前：１３２人目の素数さん mailto:sage [04/11/02 00:08:03] 566 430 名前：あぼーん mailto:あぼーん [あぼーん] あぼーん 431 名前：１３２人目の素数さん [04/11/08 10:28:08] 564 432 名前：１３２人目の素数さん [04/11/14 20:11:40] 953 433 名前：１３２人目の素数さん [04/11/19 11:36:02] 425 434 名前：１３２人目の素数さん [04/11/25 14:37:29] 368 435 名前：１３２人目の素数さん [04/11/26 01:36:14] 計算量クラスがまだわかっていない有名（無名でも可）な問題って何がある？ 436 名前：１３２人目の素数さん [04/11/27 12:34:43] かつて質問スレッドで”総音程問題(all-interval)”の解法を問うたが、結局解らなかった。 問題集のページ探せば出てる有名?解決済み問題なんだけど何やら難しいとこばかりで、、 総音程問題: 重複/欠損の無いｎ個{0,1,2...n}の要素を、その間隔(interval)に於いても重複/欠損無く全てのinterval{1〜n-1}で並べる、全ての可能性の算出。 同じintarval列をもつものは一つとみなす。 一つだけ見つける単純な方法と、原始根を使ったヤツは思いついたがそれでは 4000弱ある可能性の中のほんの5個に過ぎない。。 数列の素を求めるということで素数関係に強い人たちのスレで尋ねてみました。 437 名前：１３２人目の素数さん [04/11/27 12:38:17] >>436 意味不明。 分かるように書いてくれ。 438 名前：１３２人目の素数さん [04/11/27 13:07:05] もとい訂正します(0はややこしいので1〜nとします） n=12の場合： {1,3,12,11,9,4,8,2,5,10,6,7} ↑の各数字間の差(modulo-12で) {2,9,11,10,7,4,6,3,5,8,1} となるような数列の算出です。 439 名前：１３２人目の素数さん [04/11/27 15:11:15] 所謂差集合ですか?　だとしたら、 science3.2ch.net/test/read.cgi/math/1078820583/225 で紹介された本にあります。 440 名前：伊丹公理 [04/11/27 15:59:48] 差集合も知らんのか この馬鹿や労 441 名前：１３２人目の素数さん mailto:sage [04/11/28 00:35:23] 差集合は関係ないと思うが・・それほど単純な問題では無いと思うが 442 名前：１３２人目の素数さん mailto:sage [04/12/02 03:57:25] all-intはベンチマークに使われる類らしい。 443 名前：１３２人目の素数さん [04/12/09 06:54:54] 602 444 名前：１３２人目の素数さん [04/12/16 16:42:01] 117 445 名前：１３２人目の素数さん [04/12/23 09:51:00] 525 446 名前：１３２人目の素数さん [04/12/27 18:04:48] 633 447 名前：１３２人目の素数さん [04/12/30 19:11:43] 802 448 名前：１３２人目の素数さん mailto:sage [05/02/02 18:07:50 ] 日本語解説サイトの人がWikipediaにも書いてくれてたのね AKS素数判定法 ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 449 名前：１３２人目の素数さん mailto:sage [05/02/16 13:16:00 ] 722 450 名前：１３２人目の素数さん [05/02/25 11:49:03 ] 990 451 名前：１３２人目の素数さん [05/03/07 12:43:20 ] 886 452 名前：１３２人目の素数さん [05/03/17 17:54:15 ] 615 453 名前：１３２人目の素数さん [2005/03/29(火) 14:33:47 ] 951 454 名前：１３２人目の素数さん [2005/04/13(水) 19:51:01 ] 746 455 名前：１３２人目の素数さん [2005/04/24(日) 12:07:04 ] 数体ふるい法ってよくわからないです。 解りやすく教えてください。 456 名前：１３２人目の素数さん mailto:sage [2005/04/30(土) 06:27:04 ] >>447 スレ違いだから↓で聞いたほうがよさそう 素因数分解、素イデアル分解、一意分解整域。 science3.2ch.net/test/read.cgi/math/1082199793/ 457 名前：１３２人目の素数さん [2005/05/03(火) 02:00:02 ] age 458 名前：１３２人目の素数さん [2005/05/19(木) 15:00:13 ] 549 459 名前：１３２人目の素数さん [2005/05/25(水) 23:29:37 ] >>438 これは本当に4000個くらいしか解がないの？ 460 名前：１３２人目の素数さん [2005/06/22(水) 04:54:33 ] 128 461 名前：１３２人目の素数さん [2005/07/24(日) 02:15:16 ] 536 462 名前：１３２人目の素数さん mailto:sage [2005/07/28(木) 23:36:08 ] test 463 名前：１３２人目の素数さん [2005/07/29(金) 15:23:01 ] age 464 名前：１３２人目の素数さん mailto:sage [2005/08/08(月) 22:26:30 ] 三年二分。 465 名前：１３２人目の素数さん [2005/08/10(水) 23:07:49 ] age 466 名前：１３２人目の素数さん [2005/08/15(月) 21:25:00 ] まだ生きてたのかここw 467 名前：１３２人目の素数さん [2005/08/20(土) 21:51:13 ] 素因数分解なんて簡単でよ。 468 名前：１３２人目の素数さん mailto:sage [2005/10/03(月) 02:10:51 ] 7 469 名前：１３２人目の素数さん [2005/10/03(月) 15:46:53 ] age 470 名前：１３２人目の素数さん [2005/11/04(金) 02:17:34 ] 結局どうなの？ 471 名前：１３２人目の素数さん mailto:sage [2005/11/16(水) 23:24:20 ] >>470 何が。 472 名前：１３２人目の素数さん [2005/11/18(金) 05:35:20 ] age 473 名前：１３２人目の素数さん [2005/12/12(月) 18:44:30 ] 506 474 名前：１３２人目の素数さん mailto:sage [2006/01/02(月) 01:56:50 ] 738 475 名前：１３２人目の素数さん [2006/01/29(日) 20:32:47 ] sage 476 名前：１３２人目の素数さん [2006/01/31(火) 15:49:35 ] ラッセルの(2^(2^n)+1)でおｋ 477 名前：１３２人目の素数さん mailto:sage [2006/02/05(日) 08:30:34 ] 705 478 名前：１３２人目の素数さん mailto:sage [2006/03/02(木) 17:20:54 ] 283 479 名前：１３２人目の素数さん mailto:sage [2006/03/26(日) 13:39:43 ] 480 名前：１３２人目の素数さん [2006/03/32(土) 01:46:24 ] いくら Cn^a でも C =2^(2^10000000000000)　だったらなぁ 481 名前：１３２人目の素数さん mailto:sage [2006/04/15(土) 21:26:40 ] 482 名前：１３２人目の素数さん [2006/04/27(木) 08:18:54 ] ●素数判別法発見●暗号無効、世界パニック● 現代の暗号の基礎となっている、ハッシュ関数の逆関数を 現実時間で解を求める方法を、アメリカのＤ．Ｒ．シース博士が 発見。これにより、現在ほとんどすべての暗号が数ヶ月以内に 解読可能になる恐れが出てきた。 この発見をしたＤ．Ｒシース博士は、アメリカのＣＩＡによって 既に超法規的に拘束（一説には既に殺害されている）が、 一部の解法を記したメモが既にイスラエルに流出しているという。 現在米軍は不測の事態にそなえ、準戦争体制をとり、 既に偶発核戦争防止のための協議に入っているという。 博士の殺害について各国から非難の声が上がっているが、 政府は、「世界平和上、真にやむをえない、極めて特殊な超法規的措置である」 という声明を出している。 流出したメモは解法の一部だけしかなかったが、これを スタンフォード大学の数理学者が米軍の厳重な監視下で分析作業 をしたところ、現時点では学者としての直感的ではあるが、 博士は真に解法を発見しただろうと予想しているという。 博士は既に殺害されているが、周辺メモなどから、実際に 逆関数が導出可能であることが示されれば、世界中の数理学者の 補足研究により、数ヶ月以内に世界中で解法が発見されるだろうと いうことです。 483 名前：１３２人目の素数さん mailto:sage [2006/04/27(木) 16:17:27 ] タイトルと内容が全然違うじゃねーか もちっと勉強せい 484 名前：１３２人目の素数さん mailto:sage [2006/05/13(土) 21:20:45 ] 317 485 名前：博士 [2006/05/17(水) 01:39:16 ] 318 486 名前：１３２人目の素数さん [2006/05/23(火) 13:21:49 ] 実は長大整数の効率的な素因数分解の方法もとっくに発見されているが 発見者達は地下の別荘で隔離監視されながら、これまでどおり研究する ことだけを許されているらしい。外部との交信は常に検閲され、他人と の面会も出来ないそうだ。 487 名前：１３２人目の素数さん mailto:sage [2006/06/15(木) 23:56:42 ] 157 488 名前：１３２人目の素数さん mailto:sage [2006/07/28(金) 15:26:27 ] 724 489 名前：素数番目の素数 [2006/08/01(火) 19:13:45 ] 素数判定をしたい19728桁の自然数があるのだが、フリーソフトを利用して 判定することは可能だろうか？ 490 名前：素数番目の素数 [2006/08/02(水) 11:38:34 ] 訂正:19728桁→19729桁 491 名前：素数番目の素数 [2006/08/02(水) 17:36:47 ] 自己解決。 素数ではなかった・・・。 492 名前：１３２人目の素数さん mailto:sage [2006/08/02(水) 19:04:07 ] というか2の倍数でした・・・。 493 名前：１３２人目の素数さん [2006/08/02(水) 21:53:18 ] やっぱりＲＳＡはガセだったのか・・・みんなエシュロンに読まれっぱなし 494 名前：１３２人目の素数さん mailto:sage [2006/08/02(水) 22:50:07 ] >>492 warota とでも言ってほしいのかばかやろう 495 名前：１３２人目の素数さん [2006/08/02(水) 22:58:22 ] 素数の一般式の発見者はもう埋葬されてしまっている・・・ 496 名前：１３２人目の素数さん mailto:sage [2006/08/02(水) 23:07:58 ] そうなの？あれは誰だったっけ？ 497 名前：１３２人目の素数さん mailto:sage [2006/08/03(木) 00:22:27 ] WillansかMinác．Sierpinskiは反則気味だし。 498 名前：１３２人目の素数さん [2006/08/03(木) 23:54:12 ] 素数多項式は誰だっけ？ 499 名前：１３２人目の素数さん mailto:sage [2006/08/09(水) 03:24:30 ] 四年五時間。 500 名前：１３２人目の素数さん mailto:sage [2006/08/30(水) 16:44:40 ] 269 501 名前：１３２人目の素数さん mailto:sage [2006/09/05(火) 08:57:52 ] このアルゴリズムは例えば1万桁だとどのぐらいかかるの？ 502 名前：１３２人目の素数さん mailto:age [2006/09/21(木) 09:47:19 ] 保守 503 名前：１３２人目の素数さん mailto:sage [2006/10/03(火) 01:20:35 ] 544 504 名前：１３２人目の素数さん mailto:sage [2006/11/13(月) 00:07:07 ] 421 505 名前：１３２人目の素数さん mailto:sage [2006/12/27(水) 10:30:49 ] 976 506 名前：１３２人目の素数さん mailto:sage [2007/02/05(月) 15:46:04 ] 224 507 名前：１３２人目の素数さん mailto:sage [2007/02/07(水) 19:06:20 ] なぁ、素数っていうのは具体的に、何にどのようにどのくらい使われているんだ？ なんか暗号で使われているそうだけど、その桁数ってどのくらいあるんだ？ プログラム初心者で、課題から 素数を導き出すプログラムつくって、 ついでに判定プログラムもつくってみたけど、 どういう効能があるんだろうと疑問に思った。 508 名前：１３２人目の素数さん mailto:sage [2007/03/11(日) 14:12:52 ] 409 509 名前：１３２人目の素数さん [2007/03/11(日) 17:52:12 ] age 510 名前：１３２人目の素数さん mailto:sage [2007/05/02(水) 13:02:47 ] >>507 2^512= 512bit 2^1024= 1024bit の鍵長です。 511 名前：１３２人目の素数さん mailto:sage [2007/05/20(日) 20:22:17 ] 素数は無限にあるんでつか？ 512 名前：１３２人目の素数さん mailto:sage [2007/05/20(日) 20:23:25 ] >>511 つ　 ｢素数は無限: 6つの証明｣ www.amazon.co.jp/gp/reader/443170986X （頁をめくるには、右側のタブをクリック） science6.2ch.net/test/read.cgi/math/1166904000/619 ,592 東大入試作問者スレ８ ---------------------------------------------- M.アイグナー(著), G.M.ツィーグラー(著), 蟹江幸博(翻訳) 「天書の証明」 出版社: ｼｭﾌﾟﾘﾝｶﾞｰ･ﾌｪｱﾗｰｸ東京 価格: \3675 単行本: 313p. 出版年月: 2002/12/ ISBN-10: 443170986X ISBN-13: 978-4431709862 寸法: 21.2 x 18.6 x 2.8 cm ---------------------------------------------- 513 名前：１３２人目の素数さん mailto:sage [2007/05/24(木) 12:57:53 ] >>511 素数が有限個しか存在しないとして背理法使えばすぐ出る。 素数が有限個しか存在しないと仮定。個数をQとする。 第n番目の素数をP(n)とする。 P(1)からP(Q)までの全ての数をかけた数をMとする。 M+1はP(1)からP(Q)の全ての素数の内、いかなる素数でも割り切れない。 これは最小の素数P(1)から最大の素数P(Q)の全ての数で割り切れない数であり、「合成数」の定義からM+1は合成数では無い数である事が分かる。 また、M+1は少なくともP(Q)よりは大きい。なぜならP(1)は2であり、P(Q)は2以上であるため。 そして、素数表P(n)に存在しない数は素数ではない事は自明。 この時、数M+1は合成数でも素数でも無い数となり、これは矛盾。 よって、素数は無限に存在する。 514 名前：１３２人目の素数さん [2007/06/06(水) 20:45:28 ] 背理法はピンと来ない 515 名前：１３２人目の素数さん mailto:sage [2007/06/11(月) 01:04:13 ] VBで素数を求めるプログラムはありますかね 516 名前：１３２人目の素数さん mailto:sage [2007/06/11(月) 15:36:09 ] 作れよ。 VBは知らんけど、5〜10行程度でできるだろう。 517 名前：１３２人目の素数さん mailto:sage [2007/06/13(水) 01:34:16 ] 【nビット】 Furer 乗算【n log n 2^O(log^* n)】 science6.2ch.net/test/read.cgi/math/1181643550/ 518 名前：１３２人目の素数さん mailto:sage [2007/06/25(月) 14:14:13 ] 233 519 名前：１３２人目の素数さん [2007/07/05(木) 07:38:05 ] 背理法以外の方法…か Nから素数の集合Pへの単射写像fは…簡単に作れるか f(0),..,f(n-1)が与えられてるならf(n)はf(0)*f(1)*...*f(n-1)+1の素因数として帰納的に義すればいいし 任意の自然数が素因数分解出来る事を示すのに素数が無限個存在するのを示す必要は無いはずよね 520 名前：１３２人目の素数さん mailto:sage [2007/08/08(水) 22:24:19 ] 五年。 521 名前：１３２人目の素数さん mailto:sage [2007/08/31(金) 18:41:23 ] 522 名前：１３２人目の素数さん mailto:sage [2007/10/30(火) 12:15:55 ] 470

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef