【科学】素数判定が多項式時間で可能、コンピュータ暗号に影響大―インドの数学者証明

1 ： ◆MUMUMU4w ＠むむむφ ★：02/08/09 16:06 ID:???

カンプールのインド工科大学のManindra Agrawal、Neeraj KayalおよびNitin Saxenaが、
素数判定を多項式時間(polynomial time)で可能なアルゴリズムを発見、証明した。

素数判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
影響を及ぼすと予想される。

論文は以下のURLからたどることができる。

また、ニューヨークタイムズの記事によると、ベル研のDr. Carl Pomerance博士は
この論文を正確(correct)であると断定し、「このアルゴリズムは美しい。」
("This algorithm is beautiful.")とコメントしたという。

論文のURL(英語: 数学者の写真あり): http://www.cse.iitk.ac.in/news/primality.html
NY Timesの記事(英語): http://www.nytimes.com/2002/08/08/science/08MATH.html
(ユーザ登録(無料)が必要)
リクエスト: http://news2.2ch.net/test/read.cgi/newsplus/1028625378/768

2 ： ◆2get/BnY ：02/08/09 16:07 ID:p0Qv4ZaU

3 ： ◆MUMUMU4w ＠むむむφ ★：02/08/09 16:07 ID:???

立ててみたけど、伸びないような気がする、、、。

4 ：も：02/08/09 16:07 ID:OQfzBhUb

5 ：名無しさん＠３周年：02/08/09 16:08 ID:p0Qv4ZaU

ふむ。大変だな。

6 ：名無しさん＠３周年：02/08/09 16:09 ID:ESqhW9dO

わかんねー

7 ：名無しさん＠３周年：02/08/09 16:10 ID:Glov9+ki

もう少し原理がわかれば、このスレの重要性がわかりそうだが・・・

8 ：名無しさん＠３周年：02/08/09 16:10 ID:mHmFoITI

これ、凄いね。
暗号がパァ～

9 ：またインドか：02/08/09 16:10 ID:ebx1V6V9

RSA暗号系
http://yougo.ascii24.com/gh/20/002012.html

「インド人もビックリ」て書くヤツは5人くらいか。

10 ：名無しさん＠３周年：02/08/09 16:10 ID:o4Xc46Yt

僕の肛門もクラッキングされそうです。

11 ：名無しさん＠３周年：02/08/09 16:11 ID:G6VUzS3C

日本語にしてくれ

12 ：名無しさん＠３周年：02/08/09 16:11 ID:p0Qv4ZaU

>>6
今までは答えから問題を作り直すのがとっても難しかったけどインドの秘法を使えば簡単にできるようになるってことさ。

13 ：名無しさん＠３周年：02/08/09 16:12 ID:MJpGoiqc

わからないとおもわれあんごうにつかわれていたのがかんたんにわかるってしょうめいされたってこと？

14 ：名無しさん＠３周年：02/08/09 16:12 ID:btl0yOBV

>>11
記事を？論文を？

15 ：名無しさん＠３周年：02/08/09 16:12 ID:F3+1GL31

先をこされた

16 ：名無しさん＠３周年：02/08/09 16:12 ID:atBf2f6U

で、従来の方式に加えて何分の一に短縮されるわけ？

17 ：名無しさん＠３周年：02/08/09 16:13 ID:eQKYS3Ul

素人には分からんかもしれんが、すげーぞこの発見は。
相対性理論並みに凄い発見だ。

18 ：名無しさん＠３周年：02/08/09 16:13 ID:Tas5a1Kw

、「このインターネトは美しい。」

19 ：名無しさん＠３周年：02/08/09 16:13 ID:OhpjTS4V

インド人ｽｹﾞｰ！

20 ：名無しさん＠３周年：02/08/09 16:13 ID:NAAKb9bD

素数計算を利用したコンピュータ暗号は通常のアルゴリズムだと解析するのに
とんでもない年月がかかるので実質的に暗号解読は不可能だった。
ここで素数計算を短時間で出来るプログラムが開発されると
世界中のコンピュータ暗号が解読される危険性が出てくる。

21 ：エンリコ・プッチ：02/08/09 16:13 ID:tyNa7aUJ

素数を数えて落ち着くんだ

22 ：名無しさん＠３周年：02/08/09 16:13 ID:5jgWds5p

>>10
いつもバックドア付いてるじゃねぇかよ。

23 ：名無しさん＠３周年：02/08/09 16:13 ID:fhrxPUMy

「光速度は一定じゃない・・・」スレから移動してきたのか？
まず内容を説明してくれ。
多項式時間とはどういう意味か？
これが正しいとしてもいますぐに因数分解を使った暗号が
使いものにならなくなるというわけでもなかろう。

24 ：名無しさん＠３周年：02/08/09 16:14 ID:eQKYS3Ul

量子コンピュータなんていらんやんの世界だな

25 ：ああああ：02/08/09 16:14 ID:tbSB62TN

むふう。さすが０の発明者。

26 ：名無しさん＠３周年：02/08/09 16:14 ID:Dggrl8eM

P=NPのPの方って事か？

27 ：名無しさん＠３周年：02/08/09 16:14 ID:2TOp/07B

>もしこれが事実であった場合、
ﾊｧ? ﾊｧ? ﾊｧ?

28 ：名無しさん＠３周年：02/08/09 16:14 ID:3sZ7gTZ7

「てるくはのる」
が解明できないくせに

29 ：5/5：02/08/09 16:14 ID:QEVpRUqD

>>9
じゃー早速「インド人もビックリ」

30 ：名無しさん＠３周年：02/08/09 16:14 ID:GiRVBCuY

俺がさらしものになる日も近い

31 ：名無しさん＠３周年：02/08/09 16:14 ID:3GSD6flB

RSAピンチか？
こわっ！

32 ：名無しさん＠３周年：02/08/09 16:14 ID:5jgWds5p

やっぱインドはすげえなぁ。
0の概念を編み出したらしいし。
インドの九九は99×99ってマジ？

33 ：名無しさん＠３周年：02/08/09 16:14 ID:fq6IoeSt

あー、えーっと…よくわからん。
とりあえず発見した人お疲れさんです。
応用する人がんがってくらはい。

34 ：名無しさん＠３周年：02/08/09 16:15 ID:RRM4cE4L

よくわからんけど、やはりインドは数学のふるさと

35 ：名無しさん＠３周年：02/08/09 16:15 ID:5jgWds5p

TwoFish多用してます。

36 ：名無しさん＠3周年：02/08/09 16:15 ID:AQtnVM0o

で、この夏、俺がモテモテになったりするわけ？

37 ：バカニュース版からです：02/08/09 16:15 ID:Z5gBdXjg

えー、バカニュース版からなんでが、こちらに「皇太子様死去」という
激しく危険なスレが立っております。

みんなでこの１を逮捕に追い込みましょう！

38 ：名無しさん＠３周年：02/08/09 16:15 ID:wWevd0sD

>>14
たとえ論文を日本語にしたって、
>>11には分からんよｗ

39 ：名無しさん＠３周年：02/08/09 16:15 ID:4pxLRH9N

>>28
あれは結局暗号じゃなかったじゃん。

40 ：名無しさん＠３周年：02/08/09 16:15 ID:btl0yOBV

>>27
査読付き論文だろうと何だろうと、間違ってることはしばしばある。
Wilesによるフェルマー予想の解決も、最初は間違ってたのを
忘れたのか？

41 ：名無しさん＠３周年：02/08/09 16:15 ID:/sto7q2w

？？？

42 ：名無しさん＠３周年：02/08/09 16:16 ID:MaOZL5aX

理解できねーよ。

43 ：名無しさん＠３周年：02/08/09 16:16 ID:n9ujoYgf

インド人はすげーな

44 ：名無しさん＠３周年：02/08/09 16:16 ID:5jgWds5p

Apocalapsoが無用の長物になるのか。

ゴルゴの世界だったら発表する前にNSAに暗殺されそうだよ。

45 ：名無しさん＠３周年：02/08/09 16:16 ID:0nRfA5ch

このアルゴリズム１３行しかないぞ！

46 ：名無しさん＠３周年：02/08/09 16:16 ID:k7tpW+NF

ｎｉｔｉｎ　ｓｅｘｓｅｎａ

47 ：名無しさん＠３周年：02/08/09 16:16 ID:YujctKIX

すごいなこのインド人
ちょっと見てみたが素晴らしいアルゴリズムだ

で、素数ってウマイのか？

48 ：名無しさん＠３周年：02/08/09 16:16 ID:wspn0Hbe

さすがいんどじんのくーろんぼ

49 ：名無しさん＠３周年：02/08/09 16:17 ID:atBf2f6U

>>40
あれは査読の段階で間違いが見つかったと思われ

50 ：名無しさん＠３周年：02/08/09 16:17 ID:IuuH/Ciq

みんなの大好きなブラックホールを理論的に発見したのもインド人。

やっぱり彼等、数学強いんやねー。

51 ：名無しさん＠３周年：02/08/09 16:17 ID:Op1ZAdth

>>32
19X19

52 ：名無しさん＠３周年：02/08/09 16:17 ID:4AbuBVLM

おれが研究しようと思ってたのに！！

53 ：名無しさん＠３周年：02/08/09 16:17 ID:R26v+aBB

そのアルゴリズムが美しかったとしても、
さすがのボクチンがそれでヌクのは難しいなぁ。

54 ：名無しさん＠３周年：02/08/09 16:17 ID:25fvacxc

みんな、もっと驚けよ！！

55 ：名無しさん＠３周年：02/08/09 16:17 ID:eQKYS3Ul

だれかプログラムここに書いてくれ。そんな長く無いだろ。

56 ：名無しさん＠３周年：02/08/09 16:17 ID:jkMy87F7

やっぱインド人ってすげーなー
さすがは０を発明した国

57 ：名無しさん＠３周年：02/08/09 16:18 ID:5jgWds5p

偉大な？定理ほど美しい数式だよな。
漏れは数学苦手だったけどな。

58 ：名無しさん＠３周年：02/08/09 16:18 ID:Ool/8bWL

俺のインドイメージだと・・・

59 ：名無しさん＠３周年：02/08/09 16:18 ID:wWevd0sD

素因数分解じゃなくて、素数判定のことか。
やれやれ。

60 ：名無しさん＠３周年：02/08/09 16:18 ID:iclw/kCa

そしてそれを求めて三蔵法師が天竺に旅立ったわけか。

61 ：名無しさん＠３周年：02/08/09 16:19 ID:BlQ3Q7gl

フェルマーの定理の証明も最初は穴があったし、これはどうだろう。

62 ：名無しさん＠３周年：02/08/09 16:19 ID:n9ujoYgf

＞５０

アナルホール発見したのもインド人です

63 ：名無しさん＠３周年：02/08/09 16:19 ID:GHxKIuzP

ゴルゴ１３にも同じようなはなしなかったっけ？

64 ：名無しさん＠３周年：02/08/09 16:19 ID:wspn0Hbe

やっぱりインドと同盟を組んでチャンコ炉を滅菌すべきだ

65 ：名無しさん＠３周年：02/08/09 16:19 ID:5jgWds5p

この二人がｴｼｭﾛｿに囲い込まれるのは時間の問題か？

66 ：名無しさん＠３周年：02/08/09 16:19 ID:8K7ASHWQ

("This algorithm is beautiful.")、「このアルゴリズムは美しい。」
これしかわからん。

67 ：名無しさん＠３周年：02/08/09 16:19 ID:F3+1GL31

そもそも素数が解らない

68 ：名無しさん＠３周年：02/08/09 16:20 ID:IIo971dW

この記事が暗号じゃね－のか?

69 ：　：02/08/09 16:20 ID:kHv+xFpj

インド人は七億人もいるんだから
天才もそれだけいる
ってだけ

70 ：名無しさん＠３周年：02/08/09 16:20 ID:n9ujoYgf

＞６７
小学生ですか？

71 ：名無しさん＠３周年：02/08/09 16:20 ID:ebx1V6V9

ターミネーター2に出てきた科学者も
インド人て設定じゃなかったか?

72 ：名無しさん＠３周年：02/08/09 16:20 ID:Ool/8bWL

勇午

73 ：名無しさん＠３周年：02/08/09 16:20 ID:5jgWds5p

いまの暗号は量子コンピュータが実用化されるまで生き残ると思っていたが、
駄目になっちまったってことかな。

74 ：名無しさん＠３周年：02/08/09 16:21 ID:ic1b9H9S

　　　r⌒ヽ
　　　 |　　丶
　　　　l⌒　　＼
　　　　＼　　　＼

素数を判定するってどういうことなんですか。

75 ：名無しさん＠３周年：02/08/09 16:21 ID:gnycd9sd

よーするにだ。

素数判定（ある整数が素数であるかどうか、つまり、１とその数自体でしか割り切れないかどうか）
を判定するのに、従来は膨大な時間がかかっていた。

で、RSA などのコンピュータ暗号は、解読の過程で大量の素数判定が必要なように作られている。
そうすることで、暗号の解読に長い時間がかかるようにしていたわけ。

今回、その前提が覆されちゃったわけだ。

76 ：名無しさん＠３周年：02/08/09 16:21 ID:HGe+IZNC

やっぱ数字に強いな…
シリコンバレーで日本人がたったの数百人しかいない中、数万人も働いてるだけあるわ

77 ：名無しさん＠３周年：02/08/09 16:21 ID:jkMy87F7

>>69
中国の立場がないぞ

78 ：名無しさん＠３周年：02/08/09 16:22 ID:uLmSL57k

次世代暗号の候補あるの？

79 ：名無しさん＠３周年：02/08/09 16:22 ID:FIcgHA8/

>20
素数判定は今までも確率アルゴ使えばほぼ多項式時間で判定できてたし、
たしかリーマンの定理が正しいという前提で
多項式時間での判定ができるという証明があったはず。

難しいのは因数分解で、それじゃなきゃ影響微小なのでは？

80 ：名無しさん＠３周年：02/08/09 16:22 ID:RXKJiNgO

さすがゼロの概念を開発した国ですな

81 ：(・ε・) ◆NuNaN3vQ ：02/08/09 16:22 ID:EluUezXb

(；´Д｀)

82 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:22 ID:sGGyVNXg

ヴァーナム暗号の危機ですか？

83 ：名無しさん＠３周年：02/08/09 16:22 ID:fhrxPUMy

PGPも危ないかな?
blowfishはどうだ？

84 ：名無しさん＠３周年：02/08/09 16:22 ID:OhpjTS4V

>>77
まあ、現実は正直だってことさ…

85 ：名無しさん＠３周年：02/08/09 16:23 ID:wJgDkd8u

素数判定と素因数分解って、どのくらい違うものなのですか。
RSAの強度は素因数分解の困難さに依っているのではないかと。

86 ：名無しさん＠３周年：02/08/09 16:23 ID:wspn0Hbe

>>77
中国人は皆、馬と鹿

87 ：名無しさん＠３周年：02/08/09 16:23 ID:mjsnTRw7

これって、ＮＰ完全性の証明とは無関係？

88 ：名無しさん＠３周年：02/08/09 16:23 ID:MJpGoiqc

【驚愕】数学はインド人の陰謀だった！

89 ：名無しさん＠３周年：02/08/09 16:23 ID:fhrxPUMy

>>78
量子暗号なんてえのどうだ。

90 ：名無しさん＠３周年：02/08/09 16:23 ID:ebx1V6V9

要するに、

カレーを食えば頭が良くなる、ってこと??

91 ：名無しさん＠３周年：02/08/09 16:23 ID:atBf2f6U

印度＞中国、これ常識。
暦、仏教、哲学、数学と全部印度から中国に伝わった。その逆は一つもない。

92 ：名無しさん＠３周年：02/08/09 16:24 ID:dD58lPxB

昔、素数判定のアルゴリズムを考えたことがあるけど、恐ろしく効率が悪く
１００桁程度の数値でも数分かかったと思う。
今のＰＣだと少しは早いだろうけど、、

93 ：名無しさん＠３周年：02/08/09 16:24 ID:48hXWott

たったの１３行。

94 ：森の妖精さん：02/08/09 16:24 ID:tF4xR+34

すげーシンプルで美しい。。

95 ：名無しさん＠３周年：02/08/09 16:24 ID:ic1b9H9S

そっかー　インド人てすごいなー。

96 ：名無しさん＠３周年：02/08/09 16:24 ID:ibPN2D6X

日本も九九二十段まで教えりゃいいのに

97 ：名無しさん＠３周年：02/08/09 16:24 ID:IuuH/Ciq

>>90
「あるある」でそんな効果あるとか言いそう(w

98 ：名無しさん＠３周年：02/08/09 16:25 ID:MAV8dpHI

ハッシュが解読されるわけじゃないんだ。トリップは安心ってことか。

99 ：名無しさん＠３周年：02/08/09 16:25 ID:Zy8Id+fn

でも、何かこれだと量子を使わなくても素因数分解が出来るじゃ
ないのかと思い始めた。

100 ：名無しさん＠３周年：02/08/09 16:25 ID:4AbuBVLM

>>79
素因数分解するのに指数的時間がかからないような
理論が発明されれば、大騒ぎさ…影響微小だからこそ
にちゃんでﾜｲﾜｲやってる程度なのさ…

101 ：名無しさん＠３周年：02/08/09 16:25 ID:n9ujoYgf

さすがインドですな
これから経済的に発展したら凄いだろうねインド
日本はもっとインドに投資しる

102 ：名無しさん＠３周年：02/08/09 16:25 ID:MJpGoiqc

>>91
印度＞中国＞日本???

103 ：名無しさん＠３周年：02/08/09 16:25 ID:3sZ7gTZ7

>>91
日本の立場が…

104 ：名無しさん＠３周年：02/08/09 16:25 ID:btl0yOBV

>>55
>1 のリンク先からpdfをダウンロードしろ。
アルゴリズムの記述自体は簡単だから、英語得意じゃなくても
大丈夫。

105 ：名無しさん＠３周年：02/08/09 16:26 ID:IuuH/Ciq

単純で美しい式・・・・

アインシュタインがあの世で涙を流して喜んでるよ。

106 ：名無しさん＠３周年：02/08/09 16:26 ID:06cWWlIS

またインドか

107 ：　　　　　：02/08/09 16:26 ID:tTzB7oZg

インド工科大学は世界最難関の大学だよな

108 ：名無しさん＠３周年：02/08/09 16:26 ID:n9ujoYgf

インドこそ世界の中心になるべきだ！！
インドが親日国家で本当に良かった。。。。

109 ：名無しさん＠３周年：02/08/09 16:27 ID:gnycd9sd

インドのエリート私学（上位カーストの子弟が通うとこ）の数学のレベルはムチャクチャ高いからねえ。
徹底的に証明問題を解かせて、数学的な思考力を養ってるんだ。

レベル低いところはどこまでも低いけど、高いところはとてつもなく高い。

110 ：　：02/08/09 16:27 ID:kHv+xFpj

顔が数学者って人相だな（ｗ

111 ：謎の中国人：02/08/09 16:27 ID:wWevd0sD

中国だってインドに影響及ぼしてるあるよ。
華僑いっぱいインドにいるある。

112 ：名無しさん＠３周年：02/08/09 16:27 ID:dSbZpXUU

やはりインドは今でも特別な国なんだねぇ。
本当ならコンピュータの暗号はほとんど全滅じゃん。

113 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:28 ID:sGGyVNXg

Input: integer n > 1
1. if ( n is of the form a b , b > 1 ) output COMPOSITE;
2. r = 2;
3. while(r < n) f
4. if ( gcd(n,r) 6 = 1 ) output COMPOSITE;
5. if (r is prime)
6. let q be the largest prime factor of r

114 ：4/5：02/08/09 16:28 ID:8rRjyfr4

インド人もビックリ

115 ：名無しさん＠３周年：02/08/09 16:28 ID:gnycd9sd

つーか、ねらーってインドに好意的なのな。

116 ：名無しさん＠３周年：02/08/09 16:28 ID:IIo971dW

インディアン嘘つかないアルヨ

117 ：名無しさん＠３周年：02/08/09 16:29 ID:BlQ3Q7gl

素因数分解と素数判定は違うという意見が出てるが、そうすると

>素数判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
>ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
>影響を及ぼすと予想される。

これは何? 記事書いた奴の間違い?

118 ：名無しさん＠３周年：02/08/09 16:29 ID:btl0yOBV

論文は印刷したので、近所の喫茶店行ってゆっくり読んできまーす。
つっても専門外なのでどこまで分かるかは知らんけど。

119 ：名無しさん＠３周年：02/08/09 16:29 ID:ic1b9H9S

>110
ペヤング

120 ：名無しさん＠３周年：02/08/09 16:29 ID:6xfaNPBQ

>>111
解ったから帰れ！

121 ：名無しさん＠３周年：02/08/09 16:29 ID:MJpGoiqc

山奥で修行すると賢くなるよ

122 ：名無しさん＠３周年：02/08/09 16:30 ID:wKlonTVt

多項式時間て何？

123 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:30 ID:sGGyVNXg

124 ：　　　　　：02/08/09 16:30 ID:tTzB7oZg

>>108
その前にパキスタンと核戦争になりますｗ

125 ：名無しさん＠３周年：02/08/09 16:30 ID:JFO1+yY3

Dr. Carl Pomerance博士　は変だ

126 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:30 ID:sGGyVNXg

あれぇ！？

127 ：名無しさん＠３周年：02/08/09 16:30 ID:IIo971dW

中山式快癒器

128 ：名無しさん＠３周年：02/08/09 16:30 ID:fhrxPUMy

>>79
じゃあ、なにが大発見なのよ？
素数判定は因数分解に利用できるのではないの？

129 ：名無しさん＠３周年：02/08/09 16:31 ID:GMH4dBjN

日本の理系トップクラスはあまり数学には行きたがらないからなー。

130 ：名無しさん＠３周年：02/08/09 16:31 ID:FMEsHhol

イコールの一本多いヤツってなんですか？

131 ：名無しさん＠３周年：02/08/09 16:31 ID:G63uAr5A

頭のいいインド人ってなんかへんな感じ

132 ：名無しさん＠３周年：02/08/09 16:31 ID:OUtVNWNc

サパーリわかりまへん。
さいならー。

133 ：名無しさん＠３周年：02/08/09 16:32 ID:Ool/8bWL

インドってのは奥が深い・・・

134 ：名無しさん＠３周年：02/08/09 16:32 ID:PTG2dOxG

>>117
このアルゴリズムが多項式時間で確実に素数かそうでないかを
見分けるのなら影響は結構おおきい。

135 ：名無しさん＠３周年：02/08/09 16:33 ID:Xfkt4/Eb

多項式時間ってなんだよ？

136 ：名無しさん＠３周年：02/08/09 16:33 ID:ic1b9H9S

いつから教科書に載りますか

そしてそれは高校何年生ですか

137 ：名無しさん＠３周年：02/08/09 16:32 ID:8rRjyfr4

>>130
合同

138 ： ◆MUMUMU4w ＠むむむφ ★：02/08/09 16:32 ID:???

>>117
>>1 の日本語部分は私が創作しているので、もし >>1 に間違いや不備等がある場合、
すべて私の知識不足が原因です。

正確な内容は、>>1 からポイントした論文と英語記事を参照されると助かります。

139 ：名無しさん＠３周年：02/08/09 16:33 ID:gAYCrjve

最大の素数がわかったところで
いったい何の役に立つのだろうか？
神父の心を落ちつかせるに過ぎないではないか。

140 ：名無しさん＠３周年：02/08/09 16:33 ID:QCBJYaWB

return=0

141 ：名無しさん＠３周年：02/08/09 16:32 ID:n9ujoYgf

日本はもっと優秀なインド人を高給で雇いなさい

142 ：名無しさん＠３周年：02/08/09 16:33 ID:n9ujoYgf

なんか数学出来る奴ってカッコイイ！！

143 ：名無しさん＠３周年：02/08/09 16:34 ID:wW5+/eFD

>>129
なんで？

144 ：名無しさん＠３周年：02/08/09 16:34 ID:/h50xMoz

　　　ある意味、ミノフスキー粒子みたいな、大事変ですか？

　

145 ：名無しさん＠３周年：02/08/09 16:34 ID:GMH4dBjN

鍵になり得るかどうかを判定するのが「素数判定」
どの鍵を使うべきかを導き出すのが「因数分解」

146 ：名無しさん＠３周年：02/08/09 16:34 ID:IuuH/Ciq

>>130
＞イコールの一本多いヤツってなんですか？

「ものすげえイコール」(w

147 ：名無しさん＠３周年：02/08/09 16:34 ID:3sbAoxaL

>>130
禿同

148 ：名無しさん＠３周年：02/08/09 16:34 ID:fhrxPUMy

ところで因数分解を使っている暗号ってＲＳＡ以外になにがあるの？
教えてけれ。

149 ：名無しさん＠３周年：02/08/09 16:35 ID:mrOoAb4V

難しいんだよおまえら

そのアルゴリズムで俺様のこずかいうｐするのか？

150 ：名無しさん＠３周年：02/08/09 16:35 ID:9ODKYtz4

俺の方が先に思いついたんだけど発表が遅れちゃったよ～。
くやし～～～～～～～！！！！！

151 ：名無しさん＠３周年：02/08/09 16:35 ID:IIo971dW

インドの時代が来るって事だな？

152 ：名無しさん＠３周年：02/08/09 16:35 ID:JFO1+yY3

多項式時間はｘが増えるとｘのｎ乗で時間が増えるってことでいいの？
１０のｘ乗とかで増えるよりマシってこと？

153 ：名無しさん＠３周年：02/08/09 16:35 ID:AKcKsZY3

>頭のいいインド人ってなんかへんな感じ

０の概念を発見したのはインド人、アラビア人ではありません。
矢鱈滅多羅な天才が多い国、それがインド。

154 ：79：02/08/09 16:35 ID:FIcgHA8/

>117
＞これは何? 記事書いた奴の間違い?
明白なﾏﾁｶﾞｲ。

>128
因数分解を行う時に必要な素数を求める
ロジックが多項式時間内でできるようになった。

今までは、確率アルゴというものでほぼ多項式時間で素数か判定していた
この部分がしっかりしたものになっていたという影響っす。

だから現状の因数分解にかかる時間に及ぼす影響が微少なのでは？
といったところです。

155 ：名無しさん＠３周年：02/08/09 16:36 ID:kd1JR2pE

エラトステネスのふるい　と比べて何倍位速いのか
やってみた人は教えてくだされ。

156 ：名無しさん＠３周年：02/08/09 16:36 ID:ebx1V6V9

真紀子辞職と同時間帯に建っていたら、
すぐに埋もれただろうに。

157 ：名無しさん＠３周年：02/08/09 16:36 ID:MJpGoiqc

矢鱈滅多羅な貧乏人が多い国、それがインド。

158 ：名無しさん＠３周年：02/08/09 16:36 ID:ctDeCgg0

韓国人認定はﾏﾀﾞか？

159 ：名無しさん＠３周年：02/08/09 16:37 ID:Ool/8bWL

世界経済にプラスなんですか、マイナスなんですか。

160 ：名無しさん＠３周年：02/08/09 16:37 ID:9ODKYtz4

１０億人の人口のうち教育を受けているのが約４割、
すなわち四億人もの人々が教育を受けている。
日本の４倍の人が教育受けてんだから天才もイッパイいるさ。

161 ：名無しさん＠３周年：02/08/09 16:37 ID:oXydmKtv

牛肉喰わないのと何か関係が．．．？

162 ：名無しさん＠３周年：02/08/09 16:37 ID:FMEsHhol

>>137ｻﾝｽｸﾘｯﾄ
>>146-147ヽ(`Д´)ﾉ

163 ：名無しさん＠３周年：02/08/09 16:37 ID:8rRjyfr4

>>136
式自体は数学好きな高校2年でも読めるレベル。
まだ全部読んだわけではないが、これが合ってたら
大学受験で出るかもな。

164 ：名無しさん＠３周年：02/08/09 16:37 ID:Z42G3eIm

>>122
多項式ってのは
f(x)=ax^5+bx*4+cx^3+dx^2+ex+g　みたいの。
たとえば、桁数nの素数の場合、f(n)で計算時間が与えられることを
多項式時間で計算可能、という。

普通、桁数が増えると指数時間（4^nとか）で与えられることが多いから、
多項式時間で計算できることがわかったら、けっこう発散が遅いので
計算に有利。

165 ：名無しさん＠３周年：02/08/09 16:37 ID:FtEgm0eh

う～ん、これはエライことじゃないかなぁ。凄いんじゃないかなぁ。
微細構造定数うんぬんのニュースより遥かにとんでもないぞぉ。

166 ：名無しさん＠３周年：02/08/09 16:38 ID:LB5OPdsF

印刷し終わった。便利な世の中やね。

167 ：名無しさん＠３周年：02/08/09 16:38 ID:GMH4dBjN

>>143
数学専門になると、研究者として働ける場所が非常に限られるから。
医学とか工学とかバイオとかなら今は稼ぎもいいし、研究所もいっぱいあるけど。

168 ：名無しさん＠３周年：02/08/09 16:38 ID:na49PCld

２つの大きな素数ｐ，ｑを選択する。
ｎ＝ｐｑとφ(ｎ)＝（ｐ－１）（ｑ－１）を計算する。このｎを係数と呼ぶ。
gcd（ｅ,φ(ｎ)）＝１の関係をもつ乱数ｅ（公開指数）を選択する。ちなみにgcdとは２つの引数の最大公約数を意味する。この公開指数ｅと係数ｎが公開鍵（ｅ,ｎ）となる。
１＝ｄｅ mod φ(ｎ)となるｄ（秘密指数）を計算する。この秘密指数ｄと係数ｎが秘密鍵（ｄ,ｎ）となる。
公開鍵（ｅ,ｎ）を公開する。ｐ，ｑ，ｄは誰にも知られないようにしておく。

平文をＭ，暗号文をＣとすると，Ｍ＜ｎであれば，以下の関係式が必ず成り立ちます。
　　　　Ｃ＝Ｍ＾ｅ mod ｎ　・・・・・・（１）Ｍ＾ｅ→Ｍのe乗を表す
　　　　Ｍ＝Ｃ＾ｄ mod ｎ　・・・・・・（２）Ｃ＾ｄ→Ｃのd乗を表す
　RSA暗号の原理は，これらの関係式が必ず成り立つという数学的特性を利用しています。ただしその理由はここではあえて言及しません。
　（１）が暗号化の操作，（２）が復号化の操作をそれぞれ示しています。
　実は，ここでいくら暗号文Ｃ，係数ｎおよび公開指数ｅの値を知っていたとしても，秘密指数ｄの値を知らなければ暗号文Ｃから平文Ｍを得ることは計算量的に殆ど不可能なのです。この事がRSA暗号の安全性を保証しているわけです。

169 ：名無しさん＠３周年：02/08/09 16:39 ID:eB3syr08

理系の人間にとっては非常に興味をそそられるネタだな。専門外であっても。

170 ：名無しさん＠３周年：02/08/09 16:39 ID:IuuH/Ciq

>>161
おお！　それか！

171 ：名無しさん＠３周年：02/08/09 16:40 ID:Zy8Id+fn

とりあえずあっていたら、ＲＳＡ暗号はダメになったということだろ。
日本はいろいろ暗号提案しているから（メジャーにはならんが）、
チャンスかも。

172 ：名無しさん＠３周年：02/08/09 16:40 ID:8rRjyfr4

>>159
思考ルーチンとかに大いに役立つと思う。

173 ：名無しさん＠３周年：02/08/09 16:41 ID:ic1b9H9S

インド人が今日の２時に作った最先端の数式PDFが
２時間後に日本の地方で閲覧できて解説してもらえるなんて。

174 ：名無しさん＠３周年：02/08/09 16:41 ID:fhrxPUMy

>>169
いや、パソコン使ってるなら関係あるよ。

175 ：名無しさん＠３周年：02/08/09 16:41 ID:JVXj4GG6

インドの天才数学者ラマヌジャンについて
ttp://www.oita-med.ac.jp/campus/kenkyu/math/

ここではあまり深く触れられていないが、さまざまな数学の問題を、まったくの独学で証明していたんだそうだ。
こういうものすごい人物を生み出す国だからなあ。

176 ：名無しさん＠３周年：02/08/09 16:42 ID:J1FK8o1C

>173
それを理解できる知識も頭もあれば良かったのだが・・・・

177 ：名無しさん＠３周年：02/08/09 16:42 ID:QCBJYaWB

お釈迦様の国だから、なにが起こっても不思議ではない国。

178 ：79：02/08/09 16:43 ID:FIcgHA8/

>171
そもそもRSAの鍵というのは素数判定によって生成するんだから、
あっていたらRSAが使いやすくなるだけでは？

179 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:43 ID:sGGyVNXg

ＤＮＡ暗号という物があるらしいが

180 ：名無しさん＠３周年：02/08/09 16:43 ID:ocEfEoOA

チューリング賞もんだな

PGPもうだめぽ

181 ：名無しさん＠３周年：02/08/09 16:43 ID:MJpGoiqc

>>168
あなた天才ですね。

182 ：名無しさん＠３周年：02/08/09 16:43 ID:mcn14OWo

あぶない！そこのインド人！

　　　　　＼==========／　　　　　　　　　　　　　　　　　　＼ =========／
＼　　　　　＼=======/　　　　　　　　　　　　　　　　　　　　ゝ=======／　　　　　／==
　=＼　　　　　＼====｜　　〇　　　　　　　　　〇　　　　　｜====／　　　　　／====
　===＼　　　　　＼==｜　　　　　　 )￣￣ |　　　　　　　　　｜==／　　　　　／======
　=====＼　　　　　＼｜　　　　　　|　　　 |　　　　　　　　｜／　　　　　／========
　=======＼　　　　　ゝ　　　　　　|　　　 |　　　　　　　　　/　　　　　／==========
　=========＼　　　　　＼　　　　./⌒⌒ .|　　　　　　　／　　　　／============
　===========＼　　　　　　　　　　――┤　　　　　　　　　　　／=============
　==============＼;;;;;;;　　　　　　　　　　　　　　　　　　　　／================
　===============｜;;;;;;　　　　　　　　　　　　　　　　　　ヽ .===================
　===============｜;;;;;;　　　　　　・　　・　　　　　　　　　ヽ ==================
　===============｜;;;;;;;　　・　：：：：・　　　　　　　　　　ヽ====
　===============｜;;;;;;;;　　　：：●：：：　　　　　　　　　　`､　　　　／　ヽ┌─┐ノ　＼　　　|
　===============｜;;;;;;;;　　・：：：：：・・　　　　　　　　　　｜ `､　　 l　　　　|　　｜　　　　l　　　|　＜！？
　===============｜;;;;;;;;　　・　・　：・　　　　　　　　　　　｜　 `､　 l　　　　|　　 |　　　　 l　　　/
　===============｜;;;;;;;;　　　　　　　・　　　　　　　　　　｜　　 `､＼　　トー─|　　／　／

183 ：インド：02/08/09 16:44 ID:ebx1V6V9

なかなか気にいった　いい所だぜ

184 ：名無しさん＠３周年：02/08/09 16:44 ID:3NulSidP

>>168
うわぁ～？？？？？？？？？？？？？？？？？
わからん・・・

185 ：名無しさん＠３周年：02/08/09 16:44 ID:vaSgGztq

ここは凄いインターネットですね

186 ：名無しさん＠３周年：02/08/09 16:44 ID:X1cA8g2Y

暗号以外の大きな素数の用途ってなんかないの？

187 ：名無しさん＠３周年：02/08/09 16:44 ID:8rRjyfr4

>>178
クラッキングされやすくなんねーか？

188 ：名無しさん＠３周年：02/08/09 16:45 ID:Zy8Id+fn

>>178
ごめん、暗号詳しくないが、カギを生成しやすくなったらあてずっぽに
カギを生成して突破されるのじゃない？

189 ：名無しさん＠３周年：02/08/09 16:45 ID:B9GRbU7R

今からでも99x99までの掛け算を日々やっていこうと思います

190 ：名無しさん＠３周年：02/08/09 16:45 ID:CvwBAc+4

おれは、いま論文を手にして喜んでおります。

いや、中身は、よく分からんのよ。正直いってｗ
でも、これがアメリカの学者だったら、
いきなりネットで最新の論文を公開したり
するだろうか。

その前に弁護士に相談したり、特許取ったり、
なかなかネット上ではおがめないんじゃないかなぁ、
と思ってさｗ

191 ：名無しさん＠３周年：02/08/09 16:45 ID:31FcXzkX

これからは量子暗号

192 ：名無しさん＠３周年：02/08/09 16:45 ID:JVXj4GG6

もうひとつ、ラマヌジャンの天才を示したエピソード。
http://www.shirakami.or.jp/~eichan/oms/omsxx/oms56.html

193 ：名無しさん＠３周年：02/08/09 16:46 ID:9mZBvTN8

>>168
説明自体が暗号のようです。ｽﾏｿ

194 ：名無しさん＠３周年：02/08/09 16:46 ID:IuuH/Ciq

こういう天才的な理論と技術の積み重ねで稼動してるんだよね、
コンピューターとネットって・・・

そんな凄いものに支えられて書くことと言えば、肛門がどうしたとか
エログロのmp3がどうしたとか・・・・・ステキな世界(w

195 ：名無しさん＠３周年：02/08/09 16:46 ID:8rRjyfr4

>>190
まぁそんなもんだな。
多分アメリカが先に特許とって
この学者に謝罪と賠償もとめてくるに2000ニダー

196 ：名無しさん＠３周年：02/08/09 16:47 ID:Zy8Id+fn

量子もショルの因数分解多項式アルゴリズムでメジャーになったが、
もし、今回のように因数分解を今の機械で多項式で出来れば
余り価値がなくなる可能性大。量子コンピューターの意外に
計算パワーがないと聞いたが、どうだったけ？

197 ：名無しさん＠３周年：02/08/09 16:47 ID:fhrxPUMy

>>154
＞今までは、確率アルゴというものでほぼ多項式時間で素数か判定していた
＞この部分がしっかりしたものになっていたという影響っす。
微妙なところだな。
まだ、この関連であたらしい定理の発見がありそうだ。
影響うんぬんは今後にまかせるべきか。

198 ：名無しさん＠３周年：02/08/09 16:47 ID:NzNPzv9j

.....|ｱﾙｺﾞﾘｽﾞﾑ体操!!! |
　￣￣￣∨￣￣￣
　　　　　∧∧
　　　　（　ﾟДﾟ）
　　　⊂○　○ヽ
　　　　　|　　|￣
　　　　 / /＼＼
　　　　/ /　　> /
　　　（＿）　　∟＞

199 ：名無しさん＠３周年：02/08/09 16:48 ID:VMRf/S0H

素数ってなに？

200 ：名無しさん＠３周年：02/08/09 16:48 ID:MJpGoiqc

わたしが乗ったタクシーの番号は１７２９だったが、わたしには
その数字がつまらないものに見え、それがよくない兆しではない
ように願っているよ、とかれに言った。するとかれは『いいえ』
と反射的に答えた。『とてもおもしろい数ですよ。二つの数の立方
の和として二通りに表せる、最小の自然数です』」ラマヌジャンは
次のようにその数字を見ていたのだった。

１７２９＝１２3＋１3＝１０3＋９3

こいつ何者？

201 ：名無しさん＠３周年：02/08/09 16:48 ID:FIcgHA8/

>>188
あてずっぽに素数生成するぐらいなら1から順に割っていったほうがよっぽど速い。

202 ：名無しさん＠３周年：02/08/09 16:48 ID:3sZ7gTZ7

エイベックスのＣＤのコピーガードを説く事が出来ますか？

203 ：スゴイ：02/08/09 16:49 ID:ebx1V6V9

1000までに、ここにいる半数が理解できるように
なりそう。
有識者の方々、御疲れ様です。

204 ：名無しさん＠３周年：02/08/09 16:49 ID:eB3syr08

>>195
大っぴらに公開してしまえば特許はとれないだろ

205 ：名無しさん＠３周年：02/08/09 16:49 ID:GMH4dBjN

>>188
100万個の鍵の中から正しい２つの組み合わせを探せ！みたいなもんなので
ぜんぜん楽にならないです。

206 ：名無しさん＠３周年：02/08/09 16:49 ID:coxfyPM+

インドって、宗教の偉人が多いけど、数学の天才も多いのか。
そういや、宗教も数学も、抽象的思考と哲学が関係してるね。
常人には考え付かないことを生み出すのが得意なのかもしれない。＞インド人

207 ：名無しさん＠３周年：02/08/09 16:50 ID:AMLqiz5K

エロ画像を固めたパス付Zipも
すぐに解凍されちゃうのでせうか？

208 ：名無しさん＠３周年：02/08/09 16:50 ID:3sZ7gTZ7

ここ変のインド人はバカだよ

209 ：名無しさん＠３周年：02/08/09 16:50 ID:na49PCld

尾張徳川家の当主も暗号鍵（公開鍵）を公開してまｽﾀ
http://honor.mejiro.wide.ad.jp/~toku/pgpkey.html
http://honor.mejiro.wide.ad.jp/~toku/

210 ：名無しさん＠３周年：02/08/09 16:50 ID:ic1b9H9S

>190
本記事のＮＹタイムズの記事からしてすでに有料
むむむはタダ働きw

211 ：大阪市民( ﾟﾍﾟ)ノ ◆RAGE5ze. ：02/08/09 16:51 ID:sGGyVNXg

>>196
量子コンピュ－タが出てくれば、暗号の意味がなくなるとは言われてた
でもこのことは誰も予想だにしなかった事
マジで危なくなる　新しい暗号が早急に求められる事に
なりそう

212 ：厨国人：02/08/09 16:51 ID:vOfcjoLD

アイヤ～！こりゃチュゴクも負けてられないアルヨ。

213 ：名無しさん＠３周年：02/08/09 16:51 ID:fhrxPUMy

>>199
１と自分自身以外でしか割り切れない数。
1,3,5,7,11,13,17,19,23,,,,,,無限に続く

214 ：名無しさん＠３周年：02/08/09 16:51 ID:J1FK8o1C

>208
でも数学はスゴイかもよ。

215 ：名無しさん＠３周年：02/08/09 16:51 ID:n9ujoYgf

さすがインド
プログラマーはインド人にかぎる！！

216 ：名無しさん＠３周年：02/08/09 16:52 ID:IIo971dW

素麺ってなんですか？

217 ：名無しさん＠３周年：02/08/09 16:52 ID:mcn14OWo

　γ~三ヽ
　(三彡０ﾐ)　インド人もびっくり
　（　´∀｀）
　（_つノﾉｌ|つ
　 Lｌ_|_|_ｌ.||
　（_＿）＿）

218 ：名無しさん＠３周年：02/08/09 16:52 ID:P/CVPE4X

>>213
2を忘れてるぞ。

219 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 16:52 ID:tcY6vNRy

>>199
?????
義務教育の真最中の僕でもわかるんだが...
ネタ？

220 ：名無しさん＠３周年：02/08/09 16:52 ID:J1FK8o1C

>216
冷や麦じゃない方

221 ：名無しさん＠３周年：02/08/09 16:52 ID:EApgkzDL

数字のゼロを発明したのもインド人だったな。

222 ：名無しさん＠３周年：02/08/09 16:53 ID:B9GRbU7R

暇なときに素数を数えよう
素数を数えるときﾎﾞｸらは直感的に素数を素数だとわかるけど(一応割ってみるとかためし算をするけど)
なぜ直感的にわかるかを考えてみようと思う

223 ： ◆MUMUMU4w ＠むむむφ ★：02/08/09 16:53 ID:???

>>210
はい、ただ働きです(w。でもこのスレでこれだけのレスがつくとは。

224 ： ◆FjYmEZKc ：02/08/09 16:53 ID:cGj4N4zw

1. not≡(入力の仕方が分からん)ってなに?
2. プログラム例(…なのか?)に
　　if (r is prime)
ってあるけど, 再帰関数にしていいのか?

誰か識者がいたらオセーテ.
いまCに書き直してるけど, 数学の知識が少ないから難しい….

225 ：名無しさん＠３周年：02/08/09 16:53 ID:msWcRWbt

>>213
１は素数じゃないよ

226 ：名無しさん＠３周年：02/08/09 16:54 ID:PO7/PM62

>>223
みな一様に純粋に感動しておりまふ

227 ：名無しさん＠３周年：02/08/09 16:54 ID:5u3GHrc+

クイックソートのアルゴリズムとどっちがすごい？

228 ：名無しさん＠３周年：02/08/09 16:54 ID:PgCsgCHM

>>200
１２＾３＋１＾３＝１０＾＋９＾３
とでも書いてくれ。

229 ：名無しさん＠３周年：02/08/09 16:54 ID:FfbhwilV

>>222
>素数を数えるときﾎﾞｸらは直感的に素数を素数だとわかるけど(一応割ってみるとかためし算をするけど)

３桁以上だと自信がありませんが，何か？

230 ：名無しさん＠３周年：02/08/09 16:55 ID:J1FK8o1C

素数を言いあって遊んでる双子を見たことがあるな、テレビで。

231 ：名無しさん＠３周年：02/08/09 16:55 ID:ebx1V6V9

>>222
眠れない時は、羊を素数だけで数えよう。

232 ：名無しさん＠３周年：02/08/09 16:55 ID:jq8hqcXd

インド人もビックリ

233 ：名無しさん＠３周年：02/08/09 16:56 ID:p/ffjywi

インドすげー。

厳格な身分制度→数学で実力勝負するニダ！

って感じの努力ベクトルか？

234 ：名無しさん＠３周年：02/08/09 16:56 ID:3VUT7Q2T

　 Λ＿Λ 　　／￣￣￣￣￣￣￣￣￣￣
　<丶｀∀´> ＜　数学の起源はｳﾘﾅﾗﾆﾀﾞ!!
　（　　　　）　　＼＿＿＿＿＿＿＿＿＿＿
　｜｜　|
　〈＿フ__フ

235 ：名無しさん＠３周年：02/08/09 16:56 ID:B9GRbU7R

>>233
かっけ～

236 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 16:56 ID:tcY6vNRy

>>33
(･∀･)ｲｲ!!

237 ：名無しさん＠３周年：02/08/09 16:56 ID:eB3syr08

>>222
２や３の倍数でないというのはいいが、最小の約数が１３とか２３とかになってくるとお手上げ。

238 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 16:57 ID:tcY6vNRy

>>233の間違いだった..

239 ：名無しさん＠３周年：02/08/09 16:57 ID:8bvNM8WG

>>234
かっけ～

240 ：名無しさん＠３周年：02/08/09 16:57 ID:cQ9ibD8R

因数分解のための量子コンピューターの必要性は低下したが
量子暗号の必要性は大いに増大した

241 ：名無しさん＠３周年：02/08/09 16:57 ID:IuuH/Ciq

>>233
理論発見した人がバラモンだったらミもフタもない(w

242 ：名無しさん＠３周年：02/08/09 16:58 ID:XgR5byYz

>>231
それ昨日の夜やった！
よけい眠れなくなった

243 ：名無しさん＠３周年：02/08/09 16:58 ID:JVa2ySgw

アルゴリズム云々というレスをみて
ふと昔アルゴリズムの定理って書いていた香具師を思い出した

244 ：名無しさん＠３周年：02/08/09 16:58 ID:8rRjyfr4

暇なので素数クイ～ズ！

4198465432192251は素数か否か？

245 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 16:58 ID:tcY6vNRy

量子コンピューターってどのようなものですか？
義務教育中の僕にもわかりやすく簡潔に説明してください。

246 ：森の妖精さん：02/08/09 16:58 ID:tF4xR+34

こうなると直感だよなあ。
数学的空間が頭の中に構成されてて、
そこを線で結ぶような感じ。

多分、「考える」というよりは、
「思い」って言葉のほうが強いような
気がする。

247 ：名無しさん＠３周年：02/08/09 16:58 ID:I4z8om/h

素数判定が確定的に多項式時間で来たって
RSAの安全性には問題ないだろ。

むしろ、RSAのカギペアが作りやすくなってめでたい。

248 ：名無しさん＠３周年：02/08/09 16:58 ID:XgR5byYz

>>244
否

249 ：155：02/08/09 16:59 ID:kd1JR2pE

>>225
あのカールセーガンも「コンタクト」の原作本の中で1を素数に
しちゃってたヨ。映画では修正されてたけどネ。

250 ：名無しさん＠３周年：02/08/09 16:59 ID:5u3GHrc+

>>240
急にマトモなこと言うな！

251 ：名無しさん＠３周年：02/08/09 16:59 ID:CvwBAc+4

>>224
1.ふつうに!=でいいよ。ただし、剰余に気をつけてね。
2.再帰です。

252 ：名無しさん＠３周年：02/08/09 16:59 ID:sFRNwZ2q

>>173
そう考えると、すごい時代になったもんだよな。
ただ、数学板がもっと盛り上がってるかと思ったんだが...。

253 ：名無しさん＠３周年：02/08/09 16:59 ID:3pX2bnnW

今回の発見は>>168の秘密指数ｄがなくても簡単に計算できるようになってヤバイって話？

254 ：名無しさん＠３周年：02/08/09 16:59 ID:B9GRbU7R

>>244
>>1のアルゴリズムを脳にプログラミングするところから始めようと思います

255 ：名無しさん＠３周年：02/08/09 16:59 ID:cQ9ibD8R

>>244
素数ではない

256 ：名無しさん＠３周年：02/08/09 16:59 ID:P/CVPE4X

>>244
3で割り切れるんじゃねーの？

257 ：名無しさん＠３周年：02/08/09 16:59 ID:wKlonTVt

映画「ＣＵＢＥ」に三桁の数の素数が一瞬にわかるというやしが出てきたな。

258 ：名無しさん＠３周年：02/08/09 16:59 ID:X1cA8g2Y

>>242
眠れない夜はゴールドバッハ予想を検証しる！

259 ：85：02/08/09 16:59 ID:0WbvVOWX

>>222
>素数を数えるときﾎﾞｸらは直感的に素数を素数だとわかるけど(一応割ってみるとかためし算をするけど)

そりゃ、九九の答えを覚えてるから。
5と2の倍数で無いことが直感でわかるしね。
あとは、3の倍数、7の倍数で間を埋めてくだけ。

260 ：名無しさん＠３周年：02/08/09 16:59 ID:8rRjyfr4

>>240
低下してないよ。
量子コンピューターの方がやっぱり早い。

261 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:00 ID:tcY6vNRy

>>244
否

262 ：：02/08/09 17:00 ID:n1CqmS1a

「インド人もビックリ」って
元ネタ何でしたっけ？

263 ：名無しさん＠３周年：02/08/09 17:00 ID:lafKKDnz

RSAなんてそもそもたいした暗号じゃないことは分かってたし
これ以外の公開鍵方式が主流になるでしょう。
影響としてはそれだけのことだね。

264 ：名無しさん＠３周年：02/08/09 17:00 ID:atBf2f6U

このインド人って在印韓国同胞だろ。さすが民族偏差値トップの韓国人。

265 ：名無しさん＠３周年：02/08/09 17:00 ID:G63uAr5A

素数ってエライ！

266 ：名無しさん＠３周年：02/08/09 17:00 ID:HGe+IZNC

>>244
3で割れるじゃねーか

267 ：名無しさん＠３周年：02/08/09 17:00 ID:I4z8om/h

>>263
ネタ？

268 ：名無しさん＠３周年：02/08/09 17:01 ID:fhrxPUMy

>>218,225
ｺﾞﾒﾝﾁｬｲ
定義が正確でなかった。
「素数とは1とそれ自身のちょうど2つの約数を持つ正の整数」
2,3,5,7,9,11,13,17,19,23,.....

269 ：名無しさん＠３周年：02/08/09 17:01 ID:CvwBAc+4

>>252
むしろ、プ板のほうが漏り上がるだろー。
このネタでもうスレ上がってんのかね。

270 ：名無しさん＠３周年：02/08/09 17:02 ID:b/BWft7v

>>262
カレーのコマーシャル？

271 ：名無しさん＠３周年：02/08/09 17:02 ID:3pX2bnnW

１が素数じゃないのはなんか数学的な深い意味があるのかな？

272 ：あっさり沈むと思ったが：02/08/09 17:02 ID:ebx1V6V9

「たけしの万物創世記」という番組の第1回を観て
イイ番組だが長くはもたないだろうな、と感じた。
予想外に長寿番組になって嬉しかったが、いま同じ
ような心境。

273 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:02 ID:tcY6vNRy

>>269
プ板ってプログラムorプログラマー?

274 ：　：02/08/09 17:02 ID:yh3XqD+1

　　
　　　９　×　９　＝　８　８

275 ：名無しさん＠３周年：02/08/09 17:02 ID:3sZ7gTZ7

７は割りきれるよ

276 ：名無しさん＠３周年：02/08/09 17:03 ID:B9GRbU7R

じゃあ2chで素数をgetするのを流行らせるか
みんな3桁の素数を覚えられる(w

277 ：名無しさん＠３周年：02/08/09 17:03 ID:fGJXaN4D

>>230
俺も見た。
たしか、彼らは頭の中で素数の螺旋が出来ていて
その本数が増えて行くだけで、
それが交差しない点（する点？）が素数だとか言ってたような。

アルゴリズムがあるとは思っていたけど、
この発見て、そんなに重要なことなの？

278 ：244：02/08/09 17:03 ID:8rRjyfr4

簡単すぎたか

279 ：名無しさん＠３周年：02/08/09 17:03 ID:FfbhwilV

>>271
>１が素数じゃないのはなんか数学的な深い意味があるのかな？

「素数とは1とそれ自身のちょうど“2つ”の約数を持つ正の整数」

280 ：名無しさん＠３周年：02/08/09 17:03 ID:n9ujoYgf

＞２７４
なんすかそれは？

281 ：名無しさん＠３周年：02/08/09 17:04 ID:I4z8om/h

>>277
実用上はたいした重要じゃない。
理論的には面白いけど。

282 ：名無しさん＠３周年：02/08/09 17:04 ID:JFO1+yY3

>>273
プロレス板

283 ：名無しさん＠３周年：02/08/09 17:04 ID:GMH4dBjN

>>244
３の倍数は各桁の数字を足しても３で割り切れるってやつでしょ。

284 ：名無しさん＠３周年：02/08/09 17:04 ID:Z42G3eIm

>>273
プ板
マ板

285 ：名無しさん＠３周年：02/08/09 17:04 ID:CvwBAc+4

>>273
プログラマー板のほう。
たまに数学ネタで漏り上がるから。

286 ：名無しさん＠３周年：02/08/09 17:04 ID:nvZVzMeL

プ板=プロレス板という認識なのだが･･･
セキュ板はスレすらないね

287 ：名無しさん＠３周年：02/08/09 17:04 ID:PAEpUr1Y

>>204
それが、取れるのがアメリカ

288 ：名無しさん＠３周年：02/08/09 17:04 ID:aHX6IFiy

多項式時間て何？

289 ：名無しさん＠３周年：02/08/09 17:05 ID:HGe+IZNC

各桁じゃなく、下2桁じゃなかった？　＜3の倍数

290 ：名無しさん＠３周年：02/08/09 17:05 ID:3sZ7gTZ7

割りきれないもの　　母親の不倫

291 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:05 ID:tcY6vNRy

>>284,285
Thanks.

292 ：名無しさん＠３周年：02/08/09 17:05 ID:3pX2bnnW

>>279
２つってのがポイントか。
なぜ２つ、・・・とか言ってるときりが無いか。

293 ：名無しさん＠３周年：02/08/09 17:05 ID:I4z8om/h

>>279
その「２つ」が「１つか２つ」じゃないことに深い意味があるのかな？

294 ：名無しさん＠３周年：02/08/09 17:05 ID:HGe+IZNC

>>289
あ違う、それ４の倍数や…

295 ：名無しさん＠３周年：02/08/09 17:05 ID:MJpGoiqc

心は孤独な数学者新潮文庫

296 ：名無しさん＠３周年：02/08/09 17:05 ID:dmu9v3Mf

論文がpdfで簡単にゲットできるなんて、凄いインターネットですね

297 ：293：02/08/09 17:06 ID:I4z8om/h

>>292
ｹｺｰﾝ

298 ：269=285：02/08/09 17:06 ID:CvwBAc+4

>>284
あ、マ板っていうのか。スマソ。

299 ：名無しさん＠３周年：02/08/09 17:06 ID:J1FK8o1C

>290
それは、割り切れないと言うよりも、やり切れないのではないかと・・・

300 ：名無しさん＠３周年：02/08/09 17:06 ID:fGJXaN4D

x/1=1
x/x=1
ｘは正数

これでx=1なら二つじゃない？
「x=1」という数と「1」

多分大いに間違っているのでsage

301 ：名無しさん＠３周年：02/08/09 17:06 ID:Xtdmn+/a

チェスで負けてもこういうことは人間の出番だね

302 ：名無しさん＠３周年：02/08/09 17:06 ID:ctDeCgg0

リーマン予想はあとどのくらいで証明されますか？

303 ：名無しさん＠３周年：02/08/09 17:07 ID:FIcgHA8/

>>267
世の中の流れは楕円暗号系。

304 ：名無しさん＠３周年：02/08/09 17:07 ID:aHX6IFiy

１は素数じゃないんだよ

305 ：名無しさん＠３周年：02/08/09 17:07 ID:3VUT7Q2T

マ板はネタスレ専門だと思うが･･･

306 ：名無しさん＠３周年：02/08/09 17:08 ID:fhrxPUMy

素数は無限にある。
証明せよ。

307 ：名無しさん＠３周年：02/08/09 17:08 ID:lafKKDnz

でっかい配列用意しておいて、２の倍数、３の倍数、５の倍数と
順に潰していけば素数は簡単に見つかります

308 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:08 ID:tcY6vNRy

もし、素数が有限の場合、どうなるかをかんがえてみるといいのかな？

309 ：155：02/08/09 17:08 ID:kd1JR2pE

>>271
素因数分解が確定しない

310 ：名無しさん＠３周年：02/08/09 17:09 ID:ebx1V6V9

>>289
103は3では割り切れない模様

311 ：名無しさん＠３周年：02/08/09 17:09 ID:26T3Zl3Y

>>222
君は神ですか？
1000までなら大体素数が分かるけど、５桁超えると俺には分からん。
ましてや50桁の素数とか直感でわかるんか？

312 ：名無しさん＠３周年：02/08/09 17:09 ID:MJpGoiqc

>>262
ダンテ

313 ：名無しさん＠３周年：02/08/09 17:09 ID:MAV8dpHI

＞307
それが、エラトステネスのふるい。

314 ：名無しさん＠３周年：02/08/09 17:10 ID:B9GRbU7R

>>311
無理

315 ：sage：02/08/09 17:10 ID:PyL7nluX

>>267

316 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:10 ID:tcY6vNRy

>>307
でっかい配列ではなくて動的な配列では？

317 ：名無しさん＠３周年：02/08/09 17:11 ID:J1FK8o1C

エロホステスが不倫？

318 ：名無しさん＠３周年：02/08/09 17:11 ID:Dt7ZCjyW

????? ???? ??????? ???????
??????? ??????? ???? ?????
??? ???? ??? ??????? ????????? ????

319 ：名無しさん＠３周年：02/08/09 17:11 ID:3pX2bnnW

どっかの研究所で延々素数をはじき出して貯蔵してる場所はないんだろうか。
もしくはSETI@HOMEみたいに各家庭に配って計算してもらうとか。

320 ：名無しさん＠３周年：02/08/09 17:11 ID:fhrxPUMy

>>311
おれは３桁越えるともうわからん　ｗ
>>308
でもいいが、もっと簡単にできる模様

321 ：名無しさん＠３周年：02/08/09 17:11 ID:26T3Zl3Y

>>314
死ね。
期待して損した。

322 ：名無しさん＠３周年：02/08/09 17:11 ID:I4z8om/h

>>303
楕円曲線上の演算がどれほど安全であるのかまだ誰もわからない罠。

323 ：名無しさん＠３周年：02/08/09 17:12 ID:GMH4dBjN

>>310
103は3の倍数じゃないぞー。

324 ：名無しさん＠３周年：02/08/09 17:12 ID:HGe+IZNC

>>310
自己レスつけてるが、何か？

325 ：名無しさん＠３周年：02/08/09 17:12 ID:Q6tX6kII

193548664325686643は素数ですか？

326 ：名無しさん＠３周年：02/08/09 17:12 ID:lafKKDnz

素因数分解で一番大きな数は大きくてもルートn。
例えば96の素因数分解は2x47x47。
だからnが素数かどうか判定するのにルートnまでしか調べないですむ。

327 ：名無しさん＠３周年：02/08/09 17:12 ID:Dt7ZCjyW

&1575;&1604;&1605;&1606;&1575;&1608;&1574;

328 ：名無しさん＠３周年：02/08/09 17:12 ID:5u3GHrc+

mod ってモジュロっすか？？

329 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:12 ID:tcY6vNRy

>>320
どうやるの？
教えて。

330 ：名無しさん＠３周年：02/08/09 17:12 ID:Dka3HK/t

この掲示板は美しい。

331 ：名無しさん＠３周年：02/08/09 17:12 ID:B9GRbU7R

>>321
ｽﾏｿ

332 ：名無しさん＠３周年：02/08/09 17:12 ID:lafKKDnz

まちがった(w

333 ：名無しさん＠３周年：02/08/09 17:13 ID:0WbvVOWX

なあ、素数判定が糸口で、
因数分解が多項式時間内に説けることの証明が進むって可能性ないの？

全然別物とも思えないんだが。
こういうのは、一つ崩れるとあとは以外ともろい気がする。なんとなーーーくね。
PNもそうか？

334 ：名無しさん＠３周年：02/08/09 17:13 ID:Q6tX6kII

>>332
どんまい

335 ：名無しさん＠３周年：02/08/09 17:14 ID:I4z8om/h

>>333
ない。
風が吹けば桶屋が儲かる程度には糸口になる可能性は有るが。

336 ：名無しさん＠３周年：02/08/09 17:14 ID:fhrxPUMy

>>308
まちがえた。
その考え方でＯＫ。
最大の素数があるとして証明すればいい。

337 ：名無しさん＠３周年：02/08/09 17:14 ID:6uT+y7hp

初見でスレタイを「素敵判定が～」と読み違えたのって
漏れだけ…？(；´Д`)ﾊｱ､ｿｳﾃﾞｽｶ…

スレ内の「素数」を全部「素敵」に置き換えて音読してた
上、逝ってきまつ

338 ：名無しさん＠３周年：02/08/09 17:14 ID:u9/Zlkjd

まだ詳細は読んでないけど、アルゴリズムでってのがすごいな

339 ：名無しさん＠３周年：02/08/09 17:14 ID:J1FK8o1C

風が吹けば桶屋がもうかる：井上夢人

340 ：名無しさん＠３周年：02/08/09 17:14 ID:wJgDkd8u

サイモン・シンは取材をはじめたの？

341 ：名無しさん＠３周年：02/08/09 17:14 ID:dmu9v3Mf

【論文要約】
我々は、入力された数ｎが素数であるか合成数であるかを決定するための決定論的多項式時間アルゴリズムを示す。

342 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:14 ID:tcY6vNRy

>>336
ありがと。
これからやってみるよ。

343 ：fusiagesan：02/08/09 17:15 ID:Zm8iLNN5

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣｣
―――――――――――――‐┬┘
　　　　　　　　　　　　　　　　　 |
　　　　＿＿＿＿.＿＿＿＿　　 |
　　　　　|　　　　 | 　　　　|　　 |
　　　　　|　　　　 | ∧＿∧　|　　 |　買った直後に
　　　　　|　　　　 |（.；´Д｀）つミ | 　投げ捨てろ
　　　　　|　　　　 |/ ⊃　ﾉ　|　　 |　＿＿＿┃
　　　　￣￣￣￣'￣￣￣￣　　 |　|■　　|┃|
　　　　　　　　　　　　　　　　　　　　　　|16BIT　|
　　　　　　　　　　　　　　　　　　　　　　~~~~~~~~~

344 ：名無しさん＠３周年：02/08/09 17:15 ID:fGJXaN4D

>>337
多分そんな彼方が一番素敵。

345 ：名無しさん＠３周年：02/08/09 17:15 ID:4nS1Ocg7

>>306

素数が有限（n個）だと仮定して新しい正の整数を作る。
ただし、P[1],P[2],,,,,,P[n]はすべての素数とする。

N[n+1]=P[1]*P[2]*,,,,,,*P[n]+1
この新しく作った数N[n+1]が素数だとすると最初の仮定に矛盾する．
素数じゃないとするとP[1],P[2],,,,,,P[n]のどれかで割り切れないと駄目だが
どれで割っても１余る．よって合成数でもない．

よって最初の仮定が間違っているので
素数は無限

つーか、素数判定問題を決定的アルゴリズムで解いた学術的意味はすごいが
実用ではRSAとか解けるようになるわけじゃナイッス。

346 ：名無しさん＠３周年：02/08/09 17:15 ID:lafKKDnz

素数であるかどうかの一番高速なアルゴリズムはこれです。

return table[n];

347 ：名無しさん＠３周年：02/08/09 17:16 ID:GMH4dBjN

因数分解を多項式時間で解くとアメリカに拉致されます。

348 ：名無しさん＠３周年：02/08/09 17:16 ID:b6j1xURp

結局、これでガンダムを作れるようになるわけだ。

349 ：名無しさん＠３周年：02/08/09 17:16 ID:msWcRWbt

俺は素数ですか？

350 ：名無しさん＠３周年：02/08/09 17:16 ID:26T3Zl3Y

この論文はどういった内容なの？
だれか解説をＵＰしてくれ。

351 ：名無しさん＠３周年：02/08/09 17:16 ID:J1FK8o1C

その前にアムロを作ろう。ﾊｧﾊｧ

352 ：名無しさん＠３周年：02/08/09 17:16 ID:3VUT7Q2T

早速移植を試みてるようだ。

http://pc3.2ch.net/test/read.cgi/tech/1028877628/l50

353 ：名無しさん＠３周年：02/08/09 17:16 ID:LT4wah2T

>>222
下一桁が奇数

354 ：333：02/08/09 17:16 ID:0WbvVOWX

>>335

本当に？ちょっとｶﾞｶｰﾘ。
ヒントにならない証明を、判りやすく出来たらｷﾎﾞﾝﾇ。(説明でも可)

355 ：（ ;‘e‘）ﾁｬｰﾆｨたん ◆e3mZfiBU ：02/08/09 17:16 ID:+01tUzqf

俺は玄数を発見した

356 ：名無しさん＠３周年：02/08/09 17:16 ID:KKMyzdwO

>222　は自閉症ですか？

357 ：名無しさん＠３周年：02/08/09 17:17 ID:X1cA8g2Y

>>337
素敵は無限にあることを証明せよ(w

358 ：名無しさん＠３周年：02/08/09 17:17 ID:lafKKDnz

>>350

341 名前：名無しさん＠３周年投稿日：02/08/09 17:14 ID:dmu9v3Mf
【論文要約】
我々は、入力された数ｎが素数であるか合成数であるかを決定するための決定論的多項式時間アルゴリズムを示す。

359 ：名無しさん＠３周年：02/08/09 17:17 ID:Q6tX6kII

>>349
あなたは素敵です。

360 ：名無しさん＠３周年：02/08/09 17:17 ID:TdkaYXwd

377を素因数分解すると何になるか？

361 ：名無しさん＠３周年：02/08/09 17:17 ID:5u3GHrc+

>>346
和訳

n個のちゃぶ台をひっくり返せ;

362 ：名無しさん＠３周年：02/08/09 17:17 ID:ka1GAtlr

＞３０６
最大の素数があるとしてそれをAとしようや。
そんで、Aより小さい素数全部とAを書けた数字に1をたしてみようや。

その数字はAでもAより小さい素数全部のどれでも割れんやろ？
ということはその数字を素因数分解すれば、Aより大きい素数がでてくるっちゅう話。
矛盾。

363 ：名無しさん＠３周年：02/08/09 17:17 ID:J1FK8o1C

>349が素敵認定されますた。

364 ：名無しさん＠３周年：02/08/09 17:18 ID:IPrl879G

>>349
割リ切れるなら素数

365 ：名無しさん＠３周年：02/08/09 17:18 ID:wKlonTVt

>>337
素敵判定かぁ。
いろんなものを判定したらおもしろそうだなｗ

366 ：名無しさん＠３周年：02/08/09 17:18 ID:cQ9ibD8R

>>345
地獄狂はまだ読むな

367 ：名無しさん＠３周年：02/08/09 17:18 ID:GMH4dBjN

>>346
無効なアドレスを参照しました

368 ：名無しさん＠３周年：02/08/09 17:18 ID:fhrxPUMy

>>345
正解
>つーか、素数判定問題を決定的アルゴリズムで解いた学術的意味はすごいが
>実用ではRSAとか解けるようになるわけじゃナイッス。
ここがよくわからない。今後の発展によるか？
個人的には現在の有限の演算パワーで解けてしまうのではないかと思う。

369 ：名無しさん＠３周年：02/08/09 17:18 ID:X1cA8g2Y

>349 は現在わかっている中で最大の素敵です。

370 ：名無しさん＠３周年：02/08/09 17:19 ID:IIo971dW

俺は素敵ですか？

371 ：名無しさん＠３周年：02/08/09 17:19 ID:gKdmjNNp

何を言ってるのかさっぱりだ。
偏差値３０以下の俺にもわかるように説明ｼﾙ!

372 ：364：02/08/09 17:19 ID:IPrl879G

あ、ゴメン逆。
男女関係をお金ですっぱり割り切れる奴は非素数
小数点以下のところでずるずる引きずっちゃう奴は素数

373 ：349：02/08/09 17:19 ID:msWcRWbt

>>364
俺は割り切れない香具師です。

374 ：名無しさん＠３周年：02/08/09 17:20 ID:dmu9v3Mf

"素敵"判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
影響を及ぼすと予想される。

375 ：名無しさん＠３周年：02/08/09 17:20 ID:J1FK8o1C

>370は無敵です。

376 ：名無しさん＠３周年：02/08/09 17:20 ID:LSJYZojv

ようはコンピュータの暗号が解読されかねないってことだろ？

377 ：名無しさん＠３周年：02/08/09 17:20 ID:CvwBAc+4

素数get!

378 ：名無しさん＠３周年：02/08/09 17:20 ID:lafKKDnz

素数判定よる素敵かどうかを判定する方が難しい

379 ：名無しさん＠３周年：02/08/09 17:21 ID:GMH4dBjN

>370が無敵認定されますた

380 ：名無しさん＠３周年：02/08/09 17:21 ID:IIo971dW

＞カンプールのインド工科大学のManindra Agrawal、Neeraj KayalおよびNitin Saxenaが、
＞素敵判定を多幸式時間(polynomial time)で可能なアルゴリズムを発見、証明した。

381 ：名無しさん＠３周年：02/08/09 17:21 ID:wKlonTVt

>>345
合成数って何？

382 ：名無しさん＠３周年：02/08/09 17:21 ID:dmu9v3Mf

>>381
素数でない自然数

383 ：名無しさん＠３周年：02/08/09 17:22 ID:5u3GHrc+

もっと真面目に離散数学勉強しとけば良かった。

384 ：名無しさん＠３周年：02/08/09 17:22 ID:X1cA8g2Y

>370 は現在判明している中で最大の無敵です。

385 ：名無しさん＠３周年：02/08/09 17:22 ID:msWcRWbt

>>381
素数じゃない数字

386 ：名無しさん＠３周年：02/08/09 17:22 ID:ZQQBl7Rb

確実に/.Jで取り上げられる予感

387 ：i235071.ppp.asahi-net.or.jp：02/08/09 17:22 ID:Dggrl8eM

>>377
残念。
13*29

388 ：名無しさん＠３周年：02/08/09 17:22 ID:CvwBAc+4

>>383
いや、これは李さん数学じゃないよｗ

389 ：名無しさん＠３周年：02/08/09 17:23 ID:fGJXaN4D

有限じゃないから無限ってのが理解できない。

いや「有限でも無限でもない」って事の方が理解できないけどね。

>>381
６は２と３のってことじゃないの？

390 ：名無しさん＠３周年：02/08/09 17:23 ID:gKdmjNNp

ん？どんな暗号も解読できる何かを発見したってことなの？？
マジでわからん。（ｗ

391 ：名無しさん＠３周年：02/08/09 17:23 ID:cQ9ibD8R

最大の素敵があるとしてそれをSとしようや。
そんで、Sより小さい素敵全部とSを書けた数字に1をたしてみようや。

その数次はSでもSより小さい素敵全部のどれでも割れんやろ？
ということはその数字を素敵分解すれば、Sより大きい素敵がでてくるっちゅう話。

素敵の大きさに限りなんてないサー。

392 ：名無しさん＠３周年：02/08/09 17:23 ID:rJuc3xm9

ようは、素数判定は多項式時間でできることはわかったけど、
そのことはべつに素因数分解が高速でできるように
なることを意味しないってことですかな。

393 ：370：02/08/09 17:23 ID:IIo971dW

現在、僭越ながら私が無敵中の無敵のようですね。

394 ：名無しさん＠３周年：02/08/09 17:24 ID:J1FK8o1C

>391
俺の素敵部分は最小ですか？

395 ：名無しさん＠３周年：02/08/09 17:24 ID:aHX6IFiy

多項式時間って何？

396 ：名無しさん＠３周年：02/08/09 17:24 ID:3pX2bnnW

学生の頃は数学って面白くなかったのに
今はとても面白そうなものに見える・・・・見えるだけなんだろうな・・・

397 ：名無しさん＠３周年：02/08/09 17:24 ID:ebx1V6V9

>>324
289の誤りを指摘したかっただけです。
(私が指摘する前に、自分で訂正したようですが。)
貴方の人格を否定してるわけではないので、
怒らないで。傷ついたのなら、ゴメンね。

398 ：名無しさん＠３周年：02/08/09 17:25 ID:lafKKDnz

素数かどうかなんてテーブルつくっときゃ一発で出せるからね。
素因数分解は実際にわってみなわからんので遅いわけで

399 ：名無しさん＠３周年：02/08/09 17:25 ID:J1FK8o1C

>396
面白いと思うよ。
さっぱり解らんけど。

400 ：名無しさん＠３周年：02/08/09 17:25 ID:gKdmjNNp

頼むからお前ら日本語しゃべってくれよぉ～。（涙

401 ：377：02/08/09 17:25 ID:CvwBAc+4

>>387
あなたが因数分解するのにかかったスレ数＝10

　　　　　　　　　　　　　　　よくがんばりますた

402 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:25 ID:tcY6vNRy

やりますた。
下のであってる？
****
まず素数がN個までだと仮定する。Y[1]からY[n]は全部素数だとして
X = Y[1] * Y[2] ....... * Y[n] + 1
とする。
もしもXが素数ならば矛盾がでる。
しかし、Xが素数ではないのならばY[1]からY[n]までのどれかで割りきれるはず。
でも、どれでわってもあまりがでる。
それによっていちばん最初の過程がまちがいである。
だから素数は無限。

403 ：名無しさん＠３周年：02/08/09 17:25 ID:Q6tX6kII

素敵が有限（n人）だと仮定して新しい正の人を作る。
ただし、P[1],P[2],,,,,,P[n]はすべて素敵とする。

N[n+1]=P[1]*P[2]*,,,,,,*P[n]+1
この新しく作った人N[n+1]が素敵だとすると最初の仮定に矛盾する．
素敵じゃないとするとP[1],P[2],,,,,,P[n]のどれかで割り切れないと駄目だが
どれで割っても１人余る．よって合成人間でもない．

よって最初の仮定が間違っているので
素敵は無限

つーか、素敵判定問題を決定的アルゴリズムで解いた学術的意味はすごいが
実用では友達になれるかの判断材料になるわけじゃナイッス。

404 ：i235071.ppp.asahi-net.or.jp：02/08/09 17:25 ID:Dggrl8eM

>>394
てかIDが801

405 ：名無しさん＠３周年：02/08/09 17:26 ID:7505EEeW

映画ＣＵＢＥの知的障害者が解いてたやつ？

406 ：名無しさん＠３周年：02/08/09 17:26 ID:rJuc3xm9

>>325

In[4]:=
PrimeQ[193548664325686643]

Out[4]=
False

らしい。。

407 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:26 ID:tcY6vNRy

うあーん。
がいしゅつだった...

408 ：名無しさん＠３周年：02/08/09 17:26 ID:fhrxPUMy

>>357
もし素敵が有限ならその最大の素敵を「はあと」とします。
「はあと」＋１＞「はあと」となって、矛盾します。
したがって最大の素敵は存在しない。無限に素敵が存在します。
QED.

409 ：名無しさん＠３周年：02/08/09 17:26 ID:dmu9v3Mf

（すんごい大きい素数１）ｘ（すんごい大きい素数２）でできた数は
膨大な回数のしらみつぶし的な方法でしか因数分解できないっていう経験則が
RSAとかの暗号理論の強度を保証してたわけね。

この論文は直接それを崩すものではないけど、なんかそれに「かする」ので
ヒヤヒヤする、って感じなのかな。

410 ：名無しさん＠３周年：02/08/09 17:27 ID:J1FK8o1C

>404
ぐはっ・・・
８０１は素敵ですか？

411 ：名無しさん＠３周年：02/08/09 17:27 ID:MJpGoiqc

>>400
悪いな印度語で

412 ：名無しさん＠３周年：02/08/09 17:27 ID:Z42G3eIm

こんなスレがここまで伸びるなんて・・・
やっぱ夏休みで学生は暇なのか？

413 ：名無しさん＠３周年：02/08/09 17:27 ID:cQ9ibD8R

>>402
おめでとう正解でつ

414 ：名無しさん＠３周年：02/08/09 17:27 ID:fhrxPUMy

>>402
正解　w

415 ：i235071.ppp.asahi-net.or.jp：02/08/09 17:28 ID:Dggrl8eM

>>410
3*3*89

416 ：名無しさん＠３周年：02/08/09 17:28 ID:cQ9ibD8R

>>407
自分で証明したことに意義がある

417 ：名無しさん＠３周年：02/08/09 17:28 ID:IIo971dW

さっぱり分からない俺はネタに走るしかないんですか？
それともこの機会にこのスレで勉強した方がいいのですか？

418 ：名無しさん＠３周年：02/08/09 17:28 ID:WPnYeFxZ

わーい
これからは、素数を糞真面目に証明しなくても良くなるんだ～。
超素的ですね。PCから素数がホイホイ出て来るようになった訳で

419 ：名無しさん＠３周年：02/08/09 17:28 ID:Xtdmn+/a

>>405
障害者じゃなくてめがねの女だよ

420 ：名無しさん＠３周年：02/08/09 17:28 ID:gKdmjNNp

お前らそこまで賢いなら何で印度人に負けてんだよ！

421 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:28 ID:tcY6vNRy

みんなありがとう。

422 ：名無しさん＠３周年：02/08/09 17:29 ID:hJZzCXHR

１２８ｂｉｔ暗号なら神奈川県にある超スーパコンピュータを
上記のアルゴリズムでとけば、数分で破られてしまうということ。
数は無限でもコンピュータが扱う数は有限だから解けてしまうと言う事。
これでＦＢＩ、ＣＩＡ情報もだだ漏れだな。

423 ：名無しさん＠３周年：02/08/09 17:29 ID:MJpGoiqc

４０２のおかげでわかったよ素数

424 ：名無しさん＠３周年：02/08/09 17:30 ID:rJuc3xm9

>>422　いやだから、そうじゃなくって。。。

425 ：名無しさん＠３周年：02/08/09 17:30 ID:eB3syr08

ただ、>>402-403の方法が新しい素数を必ず作るわけでもないんだよな。
全素数積＋１が各素数より大きい複数の素数を約数に持つ場合もある。
無限性の証明としては何ら問題ないけど。

426 ：拓也 ◆rYeBoQbw ：02/08/09 17:30 ID:4rze+sEZ

>>395
判定時間が、とある体上にある多項式のサイクル内で終わるって事ですね。＞補題4.4
面白そうな論文だな・・・整数論の本でも引っ張り出してくるか

427 ：名無しさん＠３周年：02/08/09 17:30 ID:SFc6pPOS

うわっ量子コンピュータできるまで大丈夫だと思っていたのに....

428 ：名無しさん＠３周年：02/08/09 17:31 ID:KG5U6VBx

>>347
激しく笑った。

429 ：名無しさん＠３周年：02/08/09 17:32 ID:Q6tX6kII

>>425
>>403は>>345の改造です。

430 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:32 ID:tcY6vNRy

>>425
どういう意味かわからんのだが

431 ：名無しさん＠３周年：02/08/09 17:33 ID:9t3jPbDI

はいはいよかったね

432 ：モノ知らず：02/08/09 17:33 ID:IIo971dW

漁師コンピューターって実際にはどの程度現実的なものになってるの？
質問が漠然としてて申し訳ないが。

433 ：i235071.ppp.asahi-net.or.jp：02/08/09 17:33 ID:Dggrl8eM

>>430
最大と仮定された素数＜X＜生成された素数

となるような素数Xが存在するかもってことだろ。

434 ：名無しさん＠３周年：02/08/09 17:34 ID:lafKKDnz

>>432
トランジスタできて喜んでるレベル

435 ：名無しさん＠３周年：02/08/09 17:34 ID:eB3syr08

恐らく素数データベースを作って売ってる企業はあると思うけど、
その資産価値は大きく下がるかも。ただし、より大きい素数を
探しやすくなるのも事実。

436 ：名無しさん＠３周年：02/08/09 17:34 ID:KG5U6VBx

>>425
そんなわかりきったこというなヴォケ。

437 ：名無しさん＠３周年：02/08/09 17:34 ID:B5dmVCST

>>433

438 ：名無しさん＠３周年：02/08/09 17:34 ID:B5dmVCST

>>433
違う。

439 ：名無しさん＠３周年：02/08/09 17:34 ID:VUrdYPov

>>425
ええ！？問題あるんじゃあ？

440 ：名無しさん＠３周年：02/08/09 17:35 ID:I4z8om/h

>>432
魚群が発見できる程度。

441 ：名無しさん＠３周年：02/08/09 17:35 ID:2J1ElXTv

論文の中にあるΠってどういう計算の仕方するの？
Σはわかるんだけど。

442 ：432：02/08/09 17:36 ID:IIo971dW

>>434
ありがとうです
オレ的には「ずいぶん進んでるなぁ」って感じw

443 ：名無しさん＠３周年：02/08/09 17:37 ID:5u3GHrc+

>>441
集合の足し算だったりして（違　

444 ：名無しさん＠３周年：02/08/09 17:38 ID:Z42G3eIm

>>441
Σは和を計算するでしょ。同じようにΠ（パイ）は積を計算する。

445 ：名無しさん＠３周年：02/08/09 17:38 ID:X1cA8g2Y

>>441 全部かける、「総積」だと思う。Σは総和

446 ：名無しさん＠３周年：02/08/09 17:38 ID:eB3syr08

>>433
＞>>430
＞最大と仮定された素数＜X＜生成された素数
＞
＞となるような素数Xが存在するかもってことだろ。

もっと詳しく言うと、そのようなＸが生成された素数かも知れない数の
約数になってる場合がある、ということ。つまり生成されたものが
実は素数ではない、と。

447 ：拓也 ◆rYeBoQbw ：02/08/09 17:38 ID:4rze+sEZ

>>441
積です、そこで多項式になってます

448 ：名無しさん＠３周年：02/08/09 17:39 ID:fhrxPUMy

>>425
>全素数積＋１が各素数より大きい複数の素数を約数に持つ場合もある。
これはあるのかな？
>>430はそれを言ってるのだよね。

449 ：名無しさん＠３周年：02/08/09 17:39 ID:B5dmVCST

>>439
問題ないよ。実際にそうやって素数を生成してるわけじゃないから。

450 ：名無しさん＠３周年：02/08/09 17:40 ID:MJpGoiqc

プログラム板　暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/l50

数学板　素数判定は「決定的」多項式時間で可能
http://science.2ch.net/test/read.cgi/math/1028813059/l50

451 ：名無しさん＠３周年：02/08/09 17:40 ID:tY4zaA9o

暗号の歴史が変わるね

452 ：Πの定義：02/08/09 17:40 ID:mjsnTRw7

n
Π Ai = A1×A2×A3×…×An
i=1

453 ：名無しさん＠３周年：02/08/09 17:40 ID:2J1ElXTv

>>444
>>445
ｻﾝｸｽ

454 ：名無しさん＠３周年：02/08/09 17:41 ID:B5dmVCST

>>448
実際起こり得るよ。

455 ：名無しさん＠３周年：02/08/09 17:41 ID:2T+cRC0M

印度人（・∀・）

456 ：名無しさん＠３周年：02/08/09 17:42 ID:3gBHWBT7

このスレには沢山のスノッブが含まれています。

457 ：名無しさん＠３周年：02/08/09 17:42 ID:msWcRWbt

（　´∀｀）⊃⑩　
　　　素数一つください

458 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 17:42 ID:tcY6vNRy

>>454
例えばどういう場合？

459 ：　：02/08/09 17:43 ID:VSMzmnO/

あ～、ここはいつものニュー速＋板ですよね？

職業右翼もプロ市民もいないようなんですが？？？

460 ：名無しさん＠３周年：02/08/09 17:43 ID:t5knRSUj

>>402
すげえ
数学ってこんな証明の仕方してたんだね
オレ、大学では論理学だったけど、まさに論理学の応用だね
感心

461 ：　：02/08/09 17:44 ID:JFO1+yY3

⑰⊂（´∀｀　）はい、素数だよ

462 ：名無しさん＠３周年：02/08/09 17:44 ID:MJpGoiqc

>>454
素直に読むとわりあい単純な話していますが、何か？

463 ：名無しさん＠３周年：02/08/09 17:44 ID:n9cyG2tx

>>459
じゃーご要望にお答えして。
やっぱり中国と組むよりインドと組もう。

464 ：名無しさん＠３周年：02/08/09 17:45 ID:RhVAnQhw

このｽﾚは美しいな

465 ：名無しさん＠３周年：02/08/09 17:45 ID:9v05+UWz

>>402
ほへー
凄いな

466 ：プログラム板から：02/08/09 17:45 ID:hLCdZcqL

インド人のおっさんよぉ･･･
　　　　　　　はじめっからCなり何なりでコードかけよ。なぁ･･･
　　　　　　　　　　　　　　　
　　　　　　 ∧ 　　　　　　∧ 　　　　　　　 ∧
　　　　 /　ヽ　　　　　　/　ヽ_　　　　　　 / .∧
　　　　　/　　｀､　　　＿/　　｀､⌒ヾ⌒ヽ/　　∧
　　　／　　　　￣￣／　　u (.....ノ(....ノ　　　／ヽ
　　 l:::::::::　　　　　　 |　　　　　　　　　　u　.:（....ノノ
　　 |:::::::::: 　-=・=-　/￣￣ヽ　　　　　　　 ::::::::::::::／`ヽ
　　 .|:::::::::::::::::　＼_(＿＿_..ノ　　　u　 ::::::::::::::::::::(....ノノ
　　ヽ::::::::::::::::::: 　＼／ヽ　　u 　　 ::::::::::::::::::::::::::::ノ

467 ：名無しさん＠３周年：02/08/09 17:46 ID:KG5U6VBx

というか、 ID:eB3syr08さんて㌧ﾃﾞﾓですか？

>>402-403の証明で新しい素数が作られるなんて
考えてる数学者なんて全世界に一人もいませんが？
下っ端がこんなところで啓蒙活動してるんじゃねーよ。消えな、さる。

468 ：名無しさん＠３周年：02/08/09 17:46 ID:GpmaVvbk

>>450
マ板はいつものごとくすぐＣでコーディングだなぁ。

数学板は静かだねぇ。論文読んでるのかねぇ。あ、夏休みで
みな帰省中なのかｗ

469 ：名無しさん＠３周年：02/08/09 17:46 ID:vpQf/+Y7

>>441
すべて掛け合わせる

470 ：拓也 ◆rYeBoQbw ：02/08/09 17:46 ID:4rze+sEZ

にしても、
今までのユークリッドの互除法のアルゴリズム上だと、
やっぱ場合によっては無限時間になってしまうのかな？

471 ：名無しさん＠３周年：02/08/09 17:47 ID:B5dmVCST

>>458
忘れた。割と小さい素数Pに対して起こったはず。ちょっと
プログラム組んで調べるわ。

>>462
何か？

472 ：名無しさん＠３周年：02/08/09 17:47 ID:msWcRWbt

>>458
2*3*5*7*11*13+1＝30031＝59*509

473 ：名無しさん＠３周年：02/08/09 17:49 ID:fhrxPUMy

>>460
証明は論理学そのものだろ？
排中律
でも証明の排中律の多用には問題があるらしい。

474 ：名無しさん＠３周年：02/08/09 17:49 ID:B5dmVCST

あら、プログラム組む前に答え出されちゃったよ。

475 ：名無しさん＠３周年：02/08/09 17:49 ID:eB3syr08

>>467
いや？　別に数学者を対象にしてないし。
俺が中学のときにその手の本を読んでうっかり
誤解したことを書いてるだけ。
勿論証明の論理に問題がないのはわかってるよ。

476 ：名無しさん＠３周年：02/08/09 17:49 ID:96zVKmGw

>>402の証明は紀元前４世紀に証明された、と聞いたな、浪人時代に。
九大の中沢（当時名誉教授）先生から。

477 ：名無しさん＠３周年：02/08/09 17:49 ID:msWcRWbt

>>461

　　　　　　　　　　　　⑰
　　　（,,ノ゜Д゜）ノ

478 ：名無しさん＠３周年：02/08/09 17:50 ID:7bMOekbe

アメリカ政府の暗号ってTwoFishじゃ無かったっけ？
256kBだとスパコンで何分くらいで破られる？

479 ：名無しさん＠３周年：02/08/09 17:50 ID:t5knRSUj

>>473
どんな？

480 ：（課 ´ ー｀金）：02/08/09 17:52 ID:mbMae1Ff

インド人は数字に強い伝説はほんとなんだねー。
ていうか「コンピュータ暗号に影響大」以外はどういうことなのかわかんない。

481 ：名無しさん＠３周年：02/08/09 17:52 ID:fhrxPUMy

>>472
なるほど。
これでは素数の生成はできない。
証明にはなんら問題ないね。

482 ：名無しさん＠３周年：02/08/09 17:53 ID:X1cA8g2Y

多分書けないから、あらかじめ言っておこう。
>>997 最大素数ゲットおめ

483 ：名無しさん＠３周年：02/08/09 17:54 ID:FA/0IXA4

インド人怖い

484 ：名無しさん＠３周年：02/08/09 17:54 ID:kPu2H2TX

>>421 素数GETおめ

485 ：名無しさん＠３周年：02/08/09 17:54 ID:OhpjTS4V

どんな数字でも瞬時に素因数分解できる白痴の超能力者っていたら禿しくｶｺｲｲな

486 ：名無しさん＠３周年：02/08/09 17:55 ID:GMH4dBjN

>>467
マジレスすると、俺は>>402で「（全素数積＋１）＝必ず素数」になるのかと
勘違いしていたんだが、>>425のおかげで助かった。

487 ：名無しさん＠３周年：02/08/09 17:55 ID:B5dmVCST

>>480
その「コンピュータ暗号に影響大」の部分はデタラメでつ。
現時点では何とも言えない。もちろん、これをきっかけに
素因数分解を多項式時間で解くアルゴリズムが発見
されようもんなら、「コンピュータ暗号に影響大」どころの
騒ぎではなくなるけど。

488 ：名無しさん＠３周年：02/08/09 17:55 ID:kPu2H2TX

>>487　おめ

489 ：名無しさん＠３周年：02/08/09 17:55 ID:VUrdYPov

インド人って賢いんだねえ

490 ：がらすきの逆襲( ○´ー｀○)ノ ◆RAGE5ze. ：02/08/09 17:56 ID:bZdrAprR

>>482 1001だべ（違

491 ：拓也 ◆rYeBoQbw ：02/08/09 17:56 ID:4rze+sEZ

>>480
素数の判定がコンピューターの暗号に影響あるんですかね・・・
楕円関数のある有限体と解の個数でも調べるのか・・・

492 ：名無しさん＠３周年：02/08/09 17:57 ID:8rRjyfr4

>>490
この話題で1001ゲットは至難の技。

493 ：名無しさん＠３周年：02/08/09 17:57 ID:MJpGoiqc

>>477
　　　　　　　⑰
　　＿／￣￣￣＼　
　∑＿　 ∪　・∀・）
　　　　￣￣￣￣

494 ：名無しさん＠３周年：02/08/09 17:57 ID:msWcRWbt

　
　　　＼△
　　　　　⑰＼
　　　　　　□
　　　　　　/＼

495 ：名無しさん＠３周年：02/08/09 17:57 ID:GMH4dBjN

>>485
「自閉症のヤシ＝必ず特殊能力を持っている」
これってホントに正しいのかな？

496 ：名無しさん＠３周年：02/08/09 17:58 ID:Q6tX6kII

なんとしても1001取るぞ！

497 ：（≡｀ω´≡）：02/08/09 17:58 ID:FAeqyYIV

印度カリーまいう～

498 ：名無しさん＠３周年：02/08/09 17:58 ID:X1cA8g2Y

１００１＝１３＊７７

499 ：名無しさん＠３周年：02/08/09 17:58 ID:msWcRWbt

1001＝10＾3+1＾3＝（10+1）（100-10+1）＝11*91

500 ：名無しさん＠３周年：02/08/09 17:59 ID:1jM5AKGJ

すげー

501 ：名無しさん＠３周年：02/08/09 17:59 ID:fhrxPUMy

>>476
エラトステネスのことかな？

502 ：名無しさん＠３周年：02/08/09 17:59 ID:FTSaF/+q

やっぱりインドか…。

503 ：名無しさん＠３周年：02/08/09 17:59 ID:eB3syr08

突っ込んどくと1001は11の倍数。
偶数桁と奇数桁、それぞれの和の差が11の倍数になるから。

504 ：名無しさん＠３周年：02/08/09 17:59 ID:ffo8Bnb7

あのスレッドとは関係ないけど、何で田中真紀子辞任のスレないの？

505 ：名無しさん＠３周年：02/08/09 18:00 ID:6hbjrWRx

>>495
FALSE.

506 ：名無しさん＠３周年：02/08/09 18:00 ID:YeXMTarO

1001=7^1*11^1*13^1

507 ：名無しさん＠３周年：02/08/09 18:00 ID:X1cA8g2Y

1009なら素数だね。でも、そんなレス見たことねー。

508 ：名無しさん＠３周年：02/08/09 18:01 ID:fhrxPUMy

>>504
あるよ

509 ：名無しさん＠３周年：02/08/09 18:01 ID:VUrdYPov

ああそうか。（複数の素数の積＋１）＝素数とは限らないってことか。

510 ：名無しさん＠３周年：02/08/09 18:01 ID:WPnYeFxZ

　今　日　は　数　学　の　祝　日　で　す　。

511 ：名無しさん＠３周年：02/08/09 18:01 ID:Q6tX6kII

>>507
もっと行ったのあるよ

512 ：：02/08/09 18:02 ID:i+yaFbLm

もうＲＳＡは使えなくなるのか・・・
これからは楕円暗号みたいね。

513 ：名無しさん＠３周年：02/08/09 18:02 ID:ViP/E66Q

10678336399
は素数かどうか?
正解はしばらく後に｡

514 ：333：02/08/09 18:02 ID:0WbvVOWX

>>439
大丈夫。
P(1)*・・P(n)+1＝素数でない場合は、
P(1)*・・P(n)+1と、P(n）との間に素数が複数コあるから、
仮定：「P(n)を素数で最大とする」が矛盾してる。
よって、証明は成立する。

515 ：名無しさん＠３周年：02/08/09 18:02 ID:8rRjyfr4

１万とか
見た事ある

516 ：名無しさん＠３周年：02/08/09 18:02 ID:ffo8Bnb7

＞５０８
あ！ホントだ。さんくす

517 ：名無しさん＠３周年：02/08/09 18:03 ID:VUrdYPov

>>514
そうですね。さっきわかりました。さんくすこ。

518 ：名無しさん＠３周年：02/08/09 18:03 ID:pRXW9MLM

ランダウ記号でO((log n)^12)と書いているけれど・・・・

519 ：名無しさん＠３周年：02/08/09 18:03 ID:X1cA8g2Y

>551
おお、それはすげー。
じゃあ、>>1009 は神。

520 ：名無しさん＠３周年：02/08/09 18:04 ID:bMjXR073

素数判定プログラムか。懐かしいなぁ

521 ：333：02/08/09 18:05 ID:0WbvVOWX

>>495
サヴァン症候群で自閉症のﾔｼは、特殊能力持ってる事が多い。
自閉症がかならずサヴァンではない。

522 ：名無しさん＠３周年：02/08/09 18:05 ID:0k3wT/i6

>>519
クリックしてみましたが、神の姿は見えませんですた。

523 ：名無しさん＠３周年：02/08/09 18:08 ID:31FcXzkX

1001=(*^^*)

524 ：名無しさん＠３周年：02/08/09 18:08 ID:B5dmVCST

>>512
だから、なんでそうなるの。

525 ：名無しさん＠３周年：02/08/09 18:09 ID:nyKLs6+M

>>514
それだったら、
「P(1)*・・P(n)+1と、P(n）との間に素数が複数コあるから」
だけで話は終ってしまうような．．．．．

526 ：名無しさん＠３周年：02/08/09 18:09 ID:UZxYcxg/

1000までの素数

2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,
233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,
607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,
739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997

527 ：名無しさん＠３周年：02/08/09 18:09 ID:sApitvf1

>>521
ガーーーーン、ガッカリ。

528 ：名無しさん＠３周年：02/08/09 18:10 ID:VUrdYPov

>>485
映画「ＣＵＢＥ」であったな。

529 ：名無しさん＠３周年：02/08/09 18:10 ID:rJuc3xm9

>>525　P(n)を最大の素数と仮定してるから。。

530 ：名無しさん＠３周年：02/08/09 18:11 ID:+CxuR/MN

暗号が
解読されちゃうんですか？

531 ：名無しさん＠３周年：02/08/09 18:11 ID:rJuc3xm9

>>530　されません

532 ：名無しさん＠３周年：02/08/09 18:11 ID:0k3wT/i6

>>530
いや、IDが解読されちゃうんです。

533 ：名無しさん＠３周年：02/08/09 18:11 ID:X1cA8g2Y

>>526
神の暗号が埋め込まれていたりしますか？

534 ：名無しさん＠３周年：02/08/09 18:12 ID:XgR5byYz

>>530
されます

535 ：名無しさん＠３周年：02/08/09 18:12 ID:Y9p6M7EA

多項式時間・・・？？
ﾌﾟｼｭｰ

536 ：名無しさん＠３周年：02/08/09 18:12 ID:sApitvf1

>>526
よっし、これを暗記してサヴァンになろう。

537 ：名無しさん＠３周年：02/08/09 18:12 ID:I4z8om/h

<<合成数>>に１票

538 ：名無しさん＠３周年：02/08/09 18:13 ID:iF9vP6o/

●命題
人が何人か集まると、集まった人はすべて同性である

●証明
帰納法を用いる。
1人の時は自明。
k人いる時に命題が成り立つとする。
k人の人に{a1,a2,・・・a(k+1)}と名前を付ける。
この集団からa1を取り除くと残った物はk人の人の
集団であるので帰納法の仮定により{a2,・・・a(k+1)}は
すべて同性である。一方、a(k+1)を取り除くとやはり
k人の人が残るので{a1,a2,・・・ak}は同性である。
以上より、{a1,a2,・・・a(k+1)}がすべて同性である事が
示されたので、任意のnに対してn人の集団はすべて
同性である。

539 ：名無しさん＠３周年：02/08/09 18:13 ID:wKlonTVt

映画「π」を見たひといます？

540 ：名無しさん＠３周年：02/08/09 18:14 ID:VUrdYPov

＞k人の人に{a1,a2,・・・a(k+1)}と名前を付ける。
名前が一個多い。

541 ：（　゜д゜）ｳﾏｰ ◆UMAAVF96 ：02/08/09 18:14 ID:6hhi9oZd

素数は割れない。素数を数えろってAAは？

542 ：名無しさん＠３周年：02/08/09 18:15 ID:malKQn15

>>541
素数とられた・・・。鬱。

543 ：名無しさん＠３周年：02/08/09 18:16 ID:Ml8lS8Oq

>>528
でもCUBEの３桁の数って簡単で
女が計算機がなきゃ無理よ！！
なんていってたけどふつーに暗算できるじゃん
とか思ってしまった

544 ：名無しさん＠３周年：02/08/09 18:16 ID:iF9vP6o/

●命題
人が何人か集まると、集まった人はすべて同性である

●証明
帰納法を用いる。
1人の時は自明。
k人いる時に命題が成り立つとする。
k+1人の人に{a1,a2,・・・a(k+1)}と名前を付ける。
この集団からa1を取り除くと残った物はk人の人の
集団であるので帰納法の仮定により{a2,・・・a(k+1)}は
すべて同性である。一方、a(k+1)を取り除くとやはり
k人の人が残るので{a1,a2,・・・ak}は同性である。
以上より、{a1,a2,・・・a(k+1)}がすべて同性である事が
示されたので、任意のnに対してn人の集団はすべて
同性である。

545 ：名無しさん＠３周年：02/08/09 18:16 ID:2J1ElXTv

>>539
途中まで見て寝た。

546 ：名無しさん＠３周年：02/08/09 18:17 ID:rJuc3xm9

だまされそうになったけど、
k人の人に{a1,a2,・・・a(k+1)}と名前を付ける。
この集団からa1を取り除くと残った物はk人の人の
集団であるので帰納法の仮定により{a2,・・・a(k+1)}は
すべて同性である。一方、a(k+1)を取り除くとやはり
k人の人が残るので{a1,a2,・・・ak}は同性である。
以上より、{a1,a2,・・・a(k+1)}がすべて同性である事
って言うのは間違いですね、2人のときは。
3人以上だとあってるかな。>>538

547 ：名無しさん＠３周年：02/08/09 18:17 ID:0k3wT/i6

>>540
途中がとんでもなく間違ってるけど、
その部分に限っていえば、
＞k+1人の人に{a1,a2,・・・a(k+1)}と名前を付ける。
のつもりだろ。

548 ：名無しさん＠３周年：02/08/09 18:17 ID:6xfaNPBQ

>>543
思うのは誰にでも出来るよ（ｗ

549 ：名無しさん＠３周年：02/08/09 18:17 ID:msWcRWbt

　　　　　　∩
　　（,,゜д゜）　⑮

　　（,,゜д゜）⊃　⑤
　　　　　　　　③

550 ：名無しさん＠３周年：02/08/09 18:18 ID:48dp0oz7

素数というと夏華を思い出す夏。

551 ：495：02/08/09 18:18 ID:GMH4dBjN

>>521
サヴァン症候群っていうのか。ググったらいろいろためになりますた。サンクスコ。
裸の大将もサヴァンだったのね。

552 ：拓也 ◆rYeBoQbw ：02/08/09 18:18 ID:4rze+sEZ

サヴァン症候群と演算アルゴリズムと聞くと木島日記思い出すッス・・・・

553 ：名無しさん＠３周年：02/08/09 18:19 ID:eB3syr08

懐かしさで太古のディスケットを弄んでたら
こんなのが出てきたがあってるのかな…？

1 clear:cls:a=2:b=2
2 input"ｼﾗﾍﾞﾙｶｽﾞﾊ";n
3 print n;"="
4 n=int(n):if n<2 then 4
5 x=0
6 if n mod a=0 then x=x+1:n=n/a:goto 6 else if x then print "+";a;"^";x
7 if n=1 then end else if a^2>n then print "+";a:end
8 if a<6 then a=a*2-1 else a=a+b:b=2-(b=2)*2
9 goto 5

554 ：名無しさん＠３周年：02/08/09 18:19 ID:3VUT7Q2T

すすうって何ですか？

555 ：名無しさん＠３周年：02/08/09 18:20 ID:eB3syr08

って調べてみたら>>553間違ってるな（ｗ
8行はa<=3でないと。しかしなぜ間違ったまま保存してるんだろ、昔の俺。

556 ：名無しさん＠３周年：02/08/09 18:21 ID:X1cA8g2Y

>>543
素数ってのは、罠があるかないかという簡単な方の暗号で、
さらにCUBEの位置座標を知るためになにか複雑な計算が要るのではなかったカナ？

557 ：名無しさん＠３周年：02/08/09 18:21 ID:fhrxPUMy

>>538
おいおい、取り除くんでなくて増やすのだろ。

558 ：名無しさん＠３周年：02/08/09 18:21 ID:GMH4dBjN

>>543
あれって９桁じゃなかったっけ。
１２３　　　４５６　　　７８９
って感じでパネルがならんでいたような。

559 ：名無しさん＠３周年：02/08/09 18:22 ID:0k3wT/i6

>>558
９桁だったよ。

560 ：（´Д｀）テレ朝社員・岡部順一：02/08/09 18:23 ID:cZaS2mrx

・・・(ﾟ∀ﾟ)ｱﾋｬ!?

わかんねぇ。
せめて解説文のリンクをくれ！(ﾟДﾟ)

561 ：名無しさん＠３周年：02/08/09 18:23 ID:lLnJNjij

ﾜｹ(ﾟ∀ﾟ)ﾜｶﾒ

562 ：名無しさん＠３周年：02/08/09 18:24 ID:eKsC8LSL

岡部は１３階段に逝ってください

563 ：名無しさん＠３周年：02/08/09 18:25 ID:O+fhkDt0

銭湯の靴箱とか傘立てとかロッカーの番号の数って素因数分解
したくならない？
できるだけ多くの素数の掛け合わせの数だと
ラッキーな気分になる。

564 ：名無しさん＠３周年：02/08/09 18:25 ID:fhrxPUMy

なんか違うぞ　藁

数学的帰納法（その１）
自然数 n を含んだ命題 P(n) を証明するには
P(1) は正しい．
すべての自然数 k について，P(k) が正しいとすれば，P(k + 1) も正しい．
という２つのことを証明すればよい．

数学的帰納法（その２）
自然数 n を含んだ命題 P(n) を証明するには
P(1) は正しい．
すべての自然数 k について，P(1), ..., P(k) が正しいとすれば，P(k + 1) も正しい．
という２つのことを証明すればよい．

565 ：名無しさん＠３周年：02/08/09 18:26 ID:nT6UowpY

だれか素数判定電卓作れる？

566 ：名無しさん＠３周年：02/08/09 18:27 ID:0k3wT/i6

>>563
やった！　オレの住基ネットの番号、素数じゃん！！

567 ：名無しさん＠３周年：02/08/09 18:27 ID:tG9ESRES

さすが、数学王国、インド

568 ：名無しさん＠３周年：02/08/09 18:27 ID:vRRZrYWu

そうっすねー

569 ：名無しさん＠３周年：02/08/09 18:27 ID:fhrxPUMy

a(1),a(2),.....a(k+1)
からひとつ取り除いても性質が変わらなくて当たり前。
なんの証明になっていない。

570 ：名無しさん＠３周年：02/08/09 18:27 ID:Q6tX6kII

そすうっすねー

571 ：名無しさん＠３周年：02/08/09 18:28 ID:X1cA8g2Y

>>563
漏れはよく切符とかの4桁の数字を
足したり引いたり掛けたり割ったりして10を作るのをやる。。
出来るとうれしい。

572 ：森の妖精さん：02/08/09 18:28 ID:tF4xR+34

どこの新聞にも載ってねぇな。
なんて日本の新聞はアホなんだろう。

573 ：名無しさん＠３周年：02/08/09 18:28 ID:Q6tX6kII

>>571
やるやる

574 ：333：02/08/09 18:29 ID:0WbvVOWX

>素数判定(が困難であること)は、RSAをはじめとする多くのコンピュータ暗号が安全である
>ことを保障しているため、もしこれが事実であった場合、コンピュータ暗号の世界に多大な
>影響を及ぼすと予想される。

ねえ、これについては、記者の誤解？
スレの上のほうでは、因数分解には直結しないって話しだったんだけど。
そこが興味深々

575 ：名無しさん＠３周年：02/08/09 18:30 ID:I4z8om/h

>>574
誤解。

576 ：名無しさん＠３周年：02/08/09 18:30 ID:Cq7Xv/WK

>>557
取り除くで合ってるよ。

>>569
そこが間違ってるんじゃない。

577 ：拓也 ◆rYeBoQbw ：02/08/09 18:30 ID:4rze+sEZ

>>563
今度は完全数を狙ってください

完全数＝約数を足しても元の数

578 ：名無しさん＠３周年：02/08/09 18:30 ID:rJuc3xm9

>>574 うん、記者の誤解だろうね。

579 ：名無しさん＠３周年：02/08/09 18:31 ID:Ml8lS8Oq

>>548
なんか恥かいた！？
と思って調べたら
おなじようなこといってるページがあって一安心
http://www.asahi-net.or.jp/~EY5K-MYHR/cube2.htm
でも内容に関係ないのでsage

580 ：名無しさん＠３周年：02/08/09 18:32 ID:P/CVPE4X

>>577
完全数ってほとんどないやん。

581 ：名無しさん＠３周年：02/08/09 18:32 ID:fhrxPUMy

>>576
釣り？

582 ：名無しさん＠３周年：02/08/09 18:33 ID:uNbmJg4V

>>557
33550336
8589869056

この辺の値にめぐり合う確率は低そう

583 ：拓也 ◆rYeBoQbw ：02/08/09 18:33 ID:4rze+sEZ

>>580
6,28,496,8128くらいですかね、ロッカー番号でありそうなの
もう次の完全数が出てこない・・・(汁

584 ：558：02/08/09 18:34 ID:GMH4dBjN

>>543
スマソ、ＣＵＢＥのアレって君が正しかったみたいです。
同じ感想の人が↓にいますた。

http://tzk-web.com/cover/red/cube/cube.html
> 素数、懐かしいですね。数学の授業以外では自分に関わってきたことなんて
> ありませんでした。数学の得意なレヴンが「３桁の数字の素数なんて、計算機が
> なきゃ分からないわ！」と怒る場面があるんです。何言ってんの、因数分解すれば
> いいじゃん、って突っ込みたくなりました。日本とカナダの教育の違いなんで
> しょうか。たしかに今じゃ計算機がないと分からないけれど（苦笑）

585 ：名無しさん＠３周年：02/08/09 18:35 ID:rJuc3xm9

a(2)=a(3)=…=a(k+1)　(等号は同姓ってことをあらわしてます)
と
a(1)=a(2)=…=a(k)
から
a(1)=a(2)=…=a(k)=a(k+1)
は、いえます。ただし、k>1のときに。
ってことでしょ。

586 ：名無しさん＠３周年：02/08/09 18:36 ID:Cq7Xv/WK

>>581
いや、単なる指摘。

k+1人から1人除いて帰納法の仮定を用いようとしてるんだから
加えても意味ない。

で、1人除いた時に「同性である」という性質が成り立つ所から
1人除く前にも同様の性質が成り立つというのが本質なのであって、
1人除いても性質が変わらないというのは見当違い。

証明のどこが間違ってるかは>>546で正解。

587 ：名無しさん＠３周年：02/08/09 18:38 ID:fhrxPUMy

>>585
a=b
b=c
よってa=c
といってるのと同じだろ？
これが帰納法か？

588 ：名無しさん＠３周年：02/08/09 18:38 ID:+CxuR/MN

素数は
１：有限なの
２：無限なの
さて、どちらが正解ですか？

589 ：名無しさん＠３周年：02/08/09 18:39 ID:2+zkOC7r

素数は無限

その証明が上にでてただろ。
素数生成の具体的な手法と勘違いしたバカがやまほどいたが。

590 ：名無しさん＠３周年：02/08/09 18:40 ID:3VUT7Q2T

インド人は頭がいーんど

591 ：名無しさん＠３周年：02/08/09 18:40 ID:I4z8om/h

>>588
素数は有限な数で、無限にあります。

592 ：名無しさん＠３周年：02/08/09 18:40 ID:Cq7Xv/WK

>>587
「任意の2人が同性であるとき、任意のn人は同性である」って
命題を>>544の解き方でやってみ。これは帰納法の簡単な
練習問題になるから。

593 ：名無しさん＠３周年：02/08/09 18:41 ID:0nRfA5ch

虚数は素数ですか？

594 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 18:41 ID:tcY6vNRy

>>590
わら

うわけねーだろ

595 ：名無しさん＠３周年：02/08/09 18:41 ID:rJuc3xm9

>>587 a=bとb=cを仮定して、a=b=cがいえるから帰納法ですよね。
>>544 で間違えてるのは、k=1からk=2にいけないってところです。

596 ：名無しさん＠３周年：02/08/09 18:42 ID:2+zkOC7r

>>593

どんな代数を考えてるんだ？

597 ：名無しさん＠３周年：02/08/09 18:42 ID:4nS1Ocg7

ハゲの人の頭に毛が一本生えてもハゲであると仮定のもとで
お前等全員ハゲってことを証明してやるぜ

nを頭髪の本数とする。(nは正の整数）

n=0　のときは明らかにハゲ
n=k　のときハゲであると仮定すると
仮定よりn=k+1の時もハゲ

よって、お前等全員ハゲ！

598 ：名無しさん＠３周年：02/08/09 18:42 ID:OuSFwulv

>>593
いえ、素敵です

599 ：名無しさん＠３周年：02/08/09 18:42 ID:fhrxPUMy

>>592
任意なら成り立つな。
ふ～んそういう命題なのか。

600 ：名無しさん＠３周年：02/08/09 18:43 ID:jDiCNoAv

インディアン嘘つかない

601 ：名無しさん＠３周年：02/08/09 18:44 ID:WPnYeFxZ

このスレは
わくわく

します。

602 ：名無しさん＠３周年：02/08/09 18:45 ID:fhrxPUMy

＞ハゲの人の頭に毛が一本生えてもハゲであると仮定のもとで
この仮定からなら当然そうなる。

603 ：地獄狂 YahooBB219017000159.bbtec.net ◆HELLs.qk ：02/08/09 18:45 ID:tcY6vNRy

> ハゲの人の頭に毛が一本生えてもハゲであると仮定のもとで
...

604 ：名無しさん＠３周年：02/08/09 18:45 ID:2+zkOC7r

素数判定がＰで、因数分解がＮＰなら、コンピュータ暗号って素敵やんってことか。

605 ：名無しさん＠３周年：02/08/09 18:45 ID:I4z8om/h

>>597
仮定によりって、どの仮定だよ（ｗ

606 ：名無しさん＠３周年：02/08/09 18:47 ID:NeNX91Yd

素数ﾀﾝ・・・

607 ：名無しさん＠３周年：02/08/09 18:47 ID:dZAiCKBy

xの3乗をx^3と書きますね。

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

nを与えられたらnと互いに素な数aを取って
多項式(x-a)^nの1次から(n-1)次までの係数がすべてnで割り切れて
a^nをnで割った余りがaならばnは素数

でもこのやりかたではn次の多項式の係数を計算しなければならず大変
よって小さい数rをうまくとって
x^rは1とする計算を間に入れてr次の多項式の計算に収めればよい。
このrの候補の取り方が最初のwhile文。
このrは小さい数ですむというのがLemma4.2の主張。
チェックaの候補もrが小さいので少しの候補ですむ。

r次以下の多項式(x-a)^rの係数の計算はFFTを使えばよいのだろう。

8ページ目には予想として、この判定は
このaは1だけのチェックでよく、
rはn^2-1の約数ではないという条件だけでよいのではないか
といっている。

608 ：名無しさん＠３周年：02/08/09 18:50 ID:dZAiCKBy

暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/76

609 ：【素】【人】 ◆cwhvZoCk ：02/08/09 18:50 ID:lGPEO1Yr

数学苦手の私にはさっぱり分かりません

610 ：名無しさん＠３周年：02/08/09 18:51 ID:+CxuR/MN

仮定は
過程で
禿にして舞うんじゃないですか？

611 ：名無しさん＠３周年：02/08/09 18:52 ID:BlQ3Q7gl

>>607
あなたプログラマー板に書き込んでる人ですか?
これだけだと、唐突過ぎてなんだか分からないんじゃない?
12行目は何なのって質問に対しての答えだよね。

612 ：名無しさん＠３周年：02/08/09 18:53 ID:GMH4dBjN

>>538
＞●命題
＞人が何人か集まると、集まった人はすべて同性である

どういうこと？このスレは皆ヤローばっかりってことですか？

613 ：333：02/08/09 18:54 ID:0WbvVOWX

もう一度聞くけど、ほんんんとーに、記者の勘違い？

素数判定がP問題で、因数分解がNP問題だから、P問題が多項式時間で
説けても影響無いのか？

影響無いことを判りやすく証明、または説明してくれる人ｷﾎﾞﾝﾇ。

614 ：名無しさん＠３周年：02/08/09 18:54 ID:4nS1Ocg7

>611
つーか、かなりわかりやすいぞ
わからんおまえがDQN

615 ：名無しさん＠３周年：02/08/09 18:54 ID:RRpcNP1f

で結局、俺は得できるの？

616 ：名無しさん＠３周年：02/08/09 18:54 ID:I4z8om/h

>>612
ｵﾏｴがヤローならね。

617 ：fusiagesan：02/08/09 18:55 ID:Zm8iLNN5

∧＿∧
（　・∀・）
（　　　　）
｜｜┐｜
｜｜(＿)Λ
（＿),'【　MD　】',.　
~~~~~~~~~~~~~~~~~~~~~~~~~

∧＿∧
（　・∀・）＜　快感！
（　　　　）
｜｜ | |　　　　ｸﾞｼｬｯ
｜｜ | ｜ ,.,'
（＿),'.(＿)',.,
~~~~~~~~~~~~~~~~~~~~~~~~~

618 ：名無しさん＠３周年：02/08/09 18:55 ID:tiGeYy03

素数ﾊｧﾊｧ

619 ：名無しさん＠３周年：02/08/09 18:55 ID:4nS1Ocg7

PってのがそもそもPolynomial（多項式）の略

620 ：名無しさん＠３周年：02/08/09 18:57 ID:Gf8wouN2

>>613
あまり問題ないです。
効率のいい鍵の作り方が開発されただけで、別に錠前側の構造が解析されたわけではないので。

621 ：名無しさん＠３周年：02/08/09 18:57 ID:I4z8om/h

>>613
家から学校まで行く道順を知っていれば簡単に行けるけど、
しらなければひどく苦労する。それが暗号の原理。
で、今回発見されたのは、家の立て方。
だから、あまり関係ない。

622 ：333：02/08/09 18:58 ID:0WbvVOWX

＞P問題が多項式時間で説けても影響無いのか？

ほんとだ。間抜けな事言ってる。逝ってきます。

623 ：333：02/08/09 19:00 ID:0WbvVOWX

いや、直接今回の証明が、暗号を説くもので無いと言うのは、理解できる。

しかるに、今回の証明のし方が、因数分解をP問題にしたり、
PN＝Pを証明したりするヒントになっちまう可能性は？

624 ：名無しさん＠３周年：02/08/09 19:03 ID:Cq7Xv/WK

>>623
それは何とも言えない。ていうか、これでもし素因数分解が
解かれても、それは素因数分解∈P が示されるだけで
P＝NPとは別物かと。あんま自身ないけど。

625 ：名無しさん＠３周年：02/08/09 19:04 ID:dZAiCKBy

>>611
そうですが、これは2ページ目のIdentity以下の所の簡単な説明です。
あとは(x-1)^7とか(x-2)^7とか自分で計算して
係数が7で割れるか確かめて見てね。
(x-1)^6の係数で6で割り切れないのはどこか探して見てくださいね。

626 ：名無しさん＠３周年：02/08/09 19:05 ID:uVOxiLkL

>>614
DQNに分かるようにお前が説明すれ

627 ：名無しさん＠３周年：02/08/09 19:05 ID:I4z8om/h

>>623
あるとしてもナンバーズの当選番号を知るヒントになる可能性と同じ程度かと。

628 ：名無しさん＠３周年：02/08/09 19:05 ID:X1cA8g2Y

NP問題だと思われていた素数判定がじつはP問題だった、
ひょっとすると素因数分解もP問題かもしれない、
ってことであってますか？

629 ：名無しさん＠3周年：02/08/09 19:07 ID:ZYykjlel

15946285749854236541281は素数でしか？

630 ：名無しさん＠３周年：02/08/09 19:08 ID:pucKyK/y

>>629
11で割り切れたぞ

631 ：名無しさん＠３周年：02/08/09 19:08 ID:ViP/E66Q

>>621
家の建て方ってより、道の作り方のほうが良くないかい｡
道の作り方を知ってたとしても、
道順を知っていることにならない｡

632 ：333：02/08/09 19:09 ID:0WbvVOWX

じゃあ、この記事書いた記者は、
完全トーシロで、誤発射って事でいいんですか？

633 ：名無しさん＠３周年：02/08/09 19:10 ID:uVOxiLkL

>>614
繰り返すがDQNに分かるようにお前が説明すれ。特にLemma 4.2は漏れも分からん。

634 ：名無しさん＠３周年：02/08/09 19:10 ID:FIcgHA8/

>>628
素数判定ってNPだと思われていたんだっけ。

みんな333の回答に含み持たせているけど、多分数学屋の性格として
可能性0と証明されたわけではないから、という点で断言しないだけで、
今回の証明が素因数分解に応用できることはないんじゃないかなあ。

635 ：名無しさん＠３周年：02/08/09 19:10 ID:X1cA8g2Y

素数と合成数の比率ってどのくらい？

636 ：名無しさん＠３周年：02/08/09 19:11 ID:4nS1Ocg7

>>633
611の説明でわからんならあきらめろ

637 ：名無しさん＠３周年：02/08/09 19:11 ID:Gf8wouN2

>>632
トーシロかどうかは解りませんが、ウッカリサンだと思います。

638 ：333：02/08/09 19:11 ID:0WbvVOWX

>>634
ありがとう。そんなかんじなわけですね。これで安心して眠れます。

639 ：名無しさん＠３周年：02/08/09 19:12 ID:uVOxiLkL

>>636
>>611でLemma4.2がどう説明できるのか教えれ。

640 ：名無しさん＠３周年：02/08/09 19:12 ID:I4z8om/h

>>631
住所選定込みの家の作り方ってことで。
道を作るって言うのは例えとしてどうかと。

641 ：名無しさん＠３周年：02/08/09 19:13 ID:ka1GAtlr

>>631
道の作り方ってより、アスファルトの製造法のほうが良くないかい｡
アスファルトの製造法を知ってたとしても、
道を作れることにならない｡

642 ：名無しさん＠３周年：02/08/09 19:17 ID:fhrxPUMy

>>635
結構数学的におもしろい問題かもね。
無理数のようにだったらおもしろいな。

643 ：名無しさん＠３周年：02/08/09 19:19 ID:Cq7Xv/WK

>>635
π(N)をN以下の素数の個数とすると、
π(N)/N ～ 1/log(N)　（N→∞）

644 ：名無しさん＠３周年：02/08/09 19:19 ID:2SL3P/78

　中学生の算數もできない大学院生（文系）ですがなんか馬鹿にしてください．

645 ：名無しさん＠３周年：02/08/09 19:20 ID:+CxuR/MN

多項式時間と
複素時間とは
どう、ちがうのですか？

646 ：名無しさん＠３周年：02/08/09 19:23 ID:X1cA8g2Y

>>643
おおお、ありがとうございます。そんな式しらなかったよ。

647 ：名無しさん＠３周年：02/08/09 19:25 ID:6OlkANtt

なんかすげースレが伸びてるからアルゴリズムが理解できたのかと
思って期待してたのに、全然じゃねーかよ！

648 ：名無しさん＠３周年：02/08/09 19:26 ID:X1cA8g2Y

>>647 素数ゲットおめ

649 ：名無しさん＠３周年：02/08/09 19:27 ID:I4z8om/h

>>647
アルゴリズムは論文に書いてあるよ。
理解できるかどうかは各人しだい。

650 ：名無しさん＠３周年：02/08/09 19:27 ID:N8/H8UWF

ｎが素数かどうかを調べるために、

　　２、３、４、５、…、と順に割り切れるかどうか試してみる、

という極めて単純なアルゴリズムでも、gcdの計算量を１とすれば、
計算量はＰのクラスに属することになってしまうんじゃないの？

件の論文のアルゴリズムはそれを改良しただけのようにみえるが…。

つまり、件の論文のアルゴリズムは全然当たりまえのことをいっているか、
もしくは、とんでもな間違いを含んでいるか、のどちらかであるような気がする。

651 ：名無しさん＠３周年：02/08/09 19:27 ID:FlzGQDKa

素数タン.....

652 ：名無しさん＠３周年：02/08/09 19:27 ID:uVOxiLkL

614 ：名無しさん＠３周年：02/08/09 18:54 ID:4nS1Ocg7
>611
つーか、かなりわかりやすいぞ
わからんおまえがDQN

653 ：名無しさん＠３周年：02/08/09 19:27 ID:PmmFpCfH

こ、このスレはマジでヤバイだろ・・・。
正直引いた・・・。

http://tmp.2ch.net/test/read.cgi/bakanews/1028823662/

Maturi has began!!!

654 ：名無しさん＠３周年：02/08/09 19:28 ID:I4z8om/h

>>650
４は必要ないでしょ。

655 ：名無しさん＠３周年：02/08/09 19:28 ID:FIcgHA8/

>>650 桁数に対する計算量でわ。

656 ：名無しさん＠３周年：02/08/09 19:29 ID:Gf8wouN2

>>647
理解できている人はわりと居ると思うのですが…

657 ：名無しさん＠３周年：02/08/09 19:30 ID:Cq7Xv/WK

>>654
合成数を省く手間を考えると、全部ひっくるめて割った方が良い。

658 ：333：02/08/09 19:30 ID:0WbvVOWX

いや、あの、、、暗号と、素数と、因数分解の関係は
理解していて、素数は作るとき、因数分解は解くときに使うのは判るんだけど、
NP完全問題とか、そういうのをギリギリまで追い詰めてる専門家が、
今回のアルゴリズムのアイデアをヒントに、(・∀・)！って事にならないかと。。。
淡い期待をしてみますた。

659 ：名無しさん＠３周年：02/08/09 19:32 ID:NKJGQ45e

ラマヌジャンやるじゃんと言ってみる。

660 ：名無しさん＠３周年：02/08/09 19:33 ID:YH/c+ctm

>>650
素数判定がPに入るということは、
ｎが素数かどうかを調べるために、
その長さ「log n」の多項式時間で判定できなければならないのでは？

661 ：名無しさん＠３周年：02/08/09 19:33 ID:j3Rfrmv3

んー、件の論文のアルゴリズムの6行目、
let q be the largest prime factor of r-1
と一言で書かれてるところ、poly時間で出来るの？

662 ：名無しさん＠３周年：02/08/09 19:35 ID:Sjb0IzXM

まったくわからん

663 ：名無しさん＠３周年：02/08/09 19:35 ID:Gf8wouN2

>>658
構成要素が早く算出できても結局最後は組み合わせの総当たりになるので…
仮に高速な解析ロジックが考案されても今回の件は殆ど無関係だと思うのでつ。

664 ：名無しさん＠３周年：02/08/09 19:35 ID:dZAiCKBy

>>650

>>607 >>625 では多項式(x-a)^nの係数がnで割り切れるかをみているのであって
nが何かで割り切れるかをみているのではないよ。

665 ：名無しさん＠３周年：02/08/09 19:35 ID:6OlkANtt

>>650
O(log(n)^12)
でlog(n)は2進数であらわしたときの桁数だから
O(桁数^12)
つまり桁数をnとするとnの多項式オーダーとなるわけですだ。

666 ：名無しさん＠３周年：02/08/09 19:36 ID:X1cA8g2Y

>>650
あー、なんとなくわかってきました。
O(N)だと思われていた素数判定がもっと簡単に判定できる、ってのがインド人の発見で、
その後の、素因数分解うんぬんはNYTimesの誤射ではないか、ってことですね。

すると、NYTimesを間に受けてそのまま報道するとバカってこと？

667 ：名無しさん＠３周年：02/08/09 19:36 ID:8rkMuMnM

まあ、それでも俺のルータはWEPをかけてないわけで。

668 ：名無しさん＠３周年：02/08/09 19:37 ID:YIW1oiFQ

ゴルゴ１３で同じような内容があったな。

669 ：名無しさん＠３周年：02/08/09 19:38 ID:uLay7T9f

>>644
ヾ(ﾟдﾟ)ﾉﾞﾊﾞｶｰ

670 ：名無しさん＠３周年：02/08/09 19:38 ID:0PV+mjmH

そんなことより母ちゃん、今日のおかずはなに？

671 ：名無しさん＠３周年：02/08/09 19:38 ID:PmmFpCfH

こ、このスレはマジでヤバイだろ・・・。
正直引いた・・・。

http://tmp.2ch.net/test/read.cgi/bakanews/1028823662/

MATURI FESTA 2002!!!!!

672 ：名無しさん＠３周年：02/08/09 19:39 ID:j3Rfrmv3

あと、5行目の
if(r is prime)
ってのもな～

673 ：名無しさん＠３周年：02/08/09 19:39 ID:dZAiCKBy

>>661
7ページ目に
The next three steps take atmost poly(log log n) steps.
と書いてあるけど実際どうするのだろうな

674 ：名無しさん＠３周年：02/08/09 19:40 ID:N8/H8UWF

>>654
> ４は必要ないでしょ。
そうなんだけど、>>650で言いたかったのは、
ｎ未満のすべての数を総当たりでも、gcdの計算量の
ことを無視してしまえばＰになってしまう、ということ。

まず最初の>>650の改良としては、>>654のいう通りに
既知の合成数をスキップする、というのがだれでも考えること。

で、件の論文ではそれを更に押し進めているだけのような気がする。

論文の２ページのアルゴリズムの９行目で、ｒ←ｒ＋１、っての
があるが、４行目から８行目のループではとくにｒをスキップ
するような記述はない。つまり７行目の判定式で探索を打ち切り
していることが肝になるわけだが、gcdの計算量を吸収できる
ほど効率的なものなんだろうか？

675 ：名無しさん＠３周年：02/08/09 19:40 ID:I4z8om/h

>>657
なるほど。

676 ：名無しさん＠３周年：02/08/09 19:41 ID:KCu1ZsXW

>>657
せめて
２，３，５，７，９，１１，１３，，，，
だろ

677 ：名無しさん＠３周年：02/08/09 19:43 ID:Cq7Xv/WK

>>676
そりゃもっともだ。

678 ：名無しさん＠３周年：02/08/09 19:43 ID:dZAiCKBy

>>672
同じく7ページ目に
The next two steps would take atmost r^1/2 poly(log log n) time in
the brute-force implementation.
とあるがbrute-force implementationとはなんだろう。

679 ：名無しさん＠３周年：02/08/09 19:44 ID:GMH4dBjN

>>632
だいぶ前の方で記者さんが断り書きを入れているので目をつむったれ。
スレそのものは割と良スレになったね。

138 ： ◆MUMUMU4w ＠むむむφ ★ ：02/08/09 16:32 ID:???
>>117
>>1 の日本語部分は私が創作しているので、もし >>1 に間違いや不備等がある場合、
すべて私の知識不足が原因です。

正確な内容は、>>1 からポイントした論文と英語記事を参照されると助かります。

680 ：名無しさん＠３周年：02/08/09 19:44 ID:YH/c+ctm

>>674
計算量がｎならば、Pではありませんよ・・・。
Poly(log n)でないと駄目。

681 ：名無しさん＠３周年：02/08/09 19:44 ID:Cq7Xv/WK

>>674
Pの意味を勘違いしてる。

682 ：名無しさん＠３周年：02/08/09 19:44 ID:uVOxiLkL

>>678
力技による実装

683 ：333：02/08/09 19:45 ID:0WbvVOWX

おおおお、もし、２ｃｈでこの証明の欠陥がﾊｹｰﾝされたら。。。。

２ちゃねらー＞＞＞＞＞インド人学者＞＞＞＞＞ベル研

最強２ちゃんねる伝説。

684 ：名無しさん＠３周年：02/08/09 19:45 ID:kRX6mQUw

>>678
「強引な実装」あたりか。

685 ：名無しさん＠３周年：02/08/09 19:45 ID:I4z8om/h

>>674
アルゴリズムが効率的かどうかはよく読んでいないから判らないけど、
計算量が多項式オーダーだよって証明出来たところが味噌なんでしょ？

686 ：名無しさん＠３周年：02/08/09 19:46 ID:dZAiCKBy

>>674
判定法のメインルーチンは12行目だよ。
rは多項式の次数の制限をつけるために計算しているのだよ。

>>607　を読んでくれ。
そして2ページ目のIdentityを読んで見てくれ。

687 ：名無しさん＠３周年：02/08/09 19:46 ID:3VUT7Q2T

>>676
9?

688 ：名無しさん＠３周年：02/08/09 19:47 ID:Gf8wouN2

>>683
それは無いです（笑

689 ：名無しさん＠３周年：02/08/09 19:48 ID:Cq7Xv/WK

>>687
合成数を取り除くためには、その為に素数判定しなきゃいけないでしょ？
だから、「N以下の素数全てで割る」よりも「N以下の全ての数で割る」方が
効率が良いわけ。ただ、2以外の偶数は明らかに合成数だから、
2と3以上√N以下の奇数全てで割り算を実行するっつーこと。

690 ：名無しさん＠３周年：02/08/09 19:48 ID:X1cA8g2Y

>>687
自然数総当りするな、せめて2と奇数だけでチェックしろ、ってことでしょ。

691 ：名無しさん＠３周年：02/08/09 19:49 ID:uVOxiLkL

>>687
>>676は１５、１７、１９、２１、２３･･･と続くのです

692 ：名無しさん＠３周年：02/08/09 19:49 ID:I4z8om/h

まあ、この際、些細な実装の話はどうでもいいんだけど。

693 ：名無しさん＠３周年：02/08/09 19:50 ID:oH8b8gi/

この素数判定法は４００年前にすでに韓国で発見されているよ。

694 ：名無しさん＠３周年：02/08/09 19:51 ID:FIcgHA8/

>>678
暗号の分野では「brute force attack」で「総当り攻撃」と訳される。
単純にループか何かで実装しろ、ということかな。

695 ：名無しさん＠３周年：02/08/09 19:51 ID:6OlkANtt

>>689
6n+1,6n-1さらには30n+1,,,でやったほうがいいとおもわれ

696 ：名無しさん＠３周年：02/08/09 19:52 ID:3VUT7Q2T

>>689 >>690 >>691
ありがと。文系人間が下手に口挟むんじゃなかった･･･。

697 ：名無しさん＠３周年：02/08/09 19:52 ID:dZAiCKBy

>>692
まぁ、多項式時間ですむかどうかは5節の
Time Complexity Analysis
にあってどのように実装するかで多項式時間ですむか
Theorem 5.1の証明で書かれているわけです。

698 ：名無しさん＠３周年：02/08/09 19:53 ID:6OlkANtt

>>661
それって素因数分解だからできないと思うよ

699 ：名無しさん＠３周年：02/08/09 19:54 ID:dZAiCKBy

>>694
ありがとう。
rが小さいからr-1の最大素因子は力技で出せるということですね。

700 ：名無しさん＠３周年：02/08/09 19:55 ID:YH/c+ctm

>>698
rが小さければOK

701 ：名無しさん＠３周年：02/08/09 19:57 ID:X1cA8g2Y

>>695
ようやく意味がわかって感動した

702 ：名無しさん＠３周年：02/08/09 19:58 ID:dZAiCKBy

>>698
rが小さいから( (log n)^6のオーダーだから)
√rから2まで割って最大素因子qを求めても
√r poly(log log n) time
で出きるということですよ。

703 ：名無しさん＠３周年：02/08/09 19:58 ID:Cq7Xv/WK

>>695
それ言い出したらキリがないから。

704 ：NSA：02/08/09 19:58 ID:70f7hOl9

前から知ってたよ！
楕円、双曲線暗号も多項式時間で解けるんだYO!

705 ：名無しさん＠３周年：02/08/09 19:59 ID:6OlkANtt

>>695
30n＋１、30n＋７、30n＋11、30n＋13、30n＋17、30n＋19、30n＋23、30n＋29 らしい

706 ：名無しさん＠３周年：02/08/09 19:59 ID:uVOxiLkL

>>695
それをどう実装するか? 2以上の奇数生成よりコストが高そう。

707 ：名無しさん＠３周年：02/08/09 20:00 ID:/XvRzMAL

イイイ
ンンン
ドドド
人人人
だだだ

708 ：名無しさん＠３周年：02/08/09 20:01 ID:uVOxiLkL

>>704
笑えない。冗談で済む保証がどこにもないから。

709 ：名無しさん＠３周年：02/08/09 20:01 ID:6OlkANtt

>>702
そのループは何回くりかえされるの？
O(n)だったらいみないわけだが。

710 ：名無しさん＠３周年：02/08/09 20:03 ID:6OlkANtt

>>706
while(){
30n＋１
30n＋７
30n＋11
30n＋13
30n＋17
30n＋19
30n＋23
30n＋29
n++
}

711 ：ていうか ◆16H8/cmo ：02/08/09 20:04 ID:T3ys6CfN

さすが０を発明したインド人。

漏れにはさっぱり。「多項式時間」って何よ？
(過去ログは見ない！)

712 ：名無しさん＠３周年：02/08/09 20:04 ID:ZVFYbUdX

過去ログ読まず、論文ナナメ読みしただけで、適当な事いうけど、

スゲェ。なんかマジに多項式時間で計算できそう。

どうすんだ＞RSA

713 ：君は何が得意？：02/08/09 20:04 ID:vkVLiHFE

民族ごとに得意な分野があるそうな。

インド人は昔から理系の頭を持っているといわれてる。数学者、物理学者の中でも天才と呼ばれるひとを何人も生んでいる。
物事を深く考え抜くことができる環境がインドにはある。仏教（人生哲学）を考え出したのもインド人。カレーライスも。
頭のよい人はずば抜けてよい。悪い人はこれまたあきれるほど悪い。

中国人は文系・商人系の頭を持ってるといわれている。世界中に散らばって、各国の政治経済の中枢を握る架橋がそれを証明する。
たしかに商売が狡すっからくてうまい。日本人がよく中国人にニセモノをつかまされたりする。またせっかく中国に進出して作った
会社をやすやすと乗っ取られたり（ヤオハンがその良い例）するのもそのことを証明している。中国人は、けっしてまわりの人間を
信用しないし、またできないという。中国４０００年というが、最近まで、中国人は無残な殺し合いを続けた歴史がある。毛沢東は
文化大革命で２０００万人の国民を殺している。そのような環境があるから、中国人は商売人として磨きがかかったのである。

世界にくらべて日本人がかなり商売がへたくそなのはやはり、生ぬるい環境のせいだといえないこともない。役人が既得権益のなかで
ろくな仕事もしないで生きられるようなところでは正義も緊張もありはしない。高度な文化を追求するには、当然、熾烈な環境が必要
となる。

日本人に本来、商才、数学・物理などの分野の才能を持っている。しかしながら才能を伸ばしていける環境が欠けている。大学生が４年間
遊んで暮らせる環境ではどう考えても、立派な遊び人しか生まれそうにない。だから、日本人は遊び道具を作らせたら世界一になれたのである。
カラオケ、ＴＶ、アニメ、ゲームはそのことを証明している。

さて、そこで皆さんは、何がしたいのだろうか。自分がしたいことができる環境が日本になければ、どうか世界に目を向けてほしい。
しかしながら、日本の中をよく見てみれば、とんでもない宝がいっぱいある。それに気付くかどうかは、皆さんしだい。

714 ：名無しさん＠３周年：02/08/09 20:06 ID:lYaCwoqF

うそだうそだうそだぁぁぁぁぁぁぁぁぁぁ
ぜぇぇぇぇぇぇったいうそだぁぁぁぁぁぁ
デマに2^64ペリカ

715 ：名無しさん＠３周年：02/08/09 20:06 ID:Cq7Xv/WK

>>712
＞どうすんだ＞RSA

どうもしないだろう。

716 ：名無しさん＠３周年：02/08/09 20:07 ID:I4z8om/h

>>712
> どうすんだ＞RSA

鍵生成が速くなってうれしい。

717 ：名無しさん＠３周年：02/08/09 20:07 ID:dZAiCKBy

>>709
rを求めるwhileループは(log n)^6のオーダーで
このr-1の最大素因子qを求めるところが√r回の割り算の繰り返し。
よってこのwhileループは√r(log n)^6 すなわち(log n)^9のオーダーの
計算量になるとTheorem　5.1の証明には書いてあるよ。

718 ：333：02/08/09 20:07 ID:0WbvVOWX

>漏れにはさっぱり。「多項式時間」って何よ？
>(過去ログは見ない！)

以外と、過去ログにも説明されていない。
計算対象の要素数が、指数になってない時間で計算できるよって事。

計算要素がちょっと増えることで、あっという間にベラボウな計算時間が要求される
タイプじゃないって事。

全部、総当りで確かめてみる(およびそれに毛の生えたような)以外の方法があるって事。

っていめーじか？

719 ：名無しさん＠３周年：02/08/09 20:08 ID:FIcgHA8/

>>710

なんとなく↓
while() {
　for(i=1; i<2; i++)
　　for(j=1; j<3; j++)
　　　for(k=1; k<5; k++)
　　　　30n + i*3*5 - 2*j*5 + 2*3*k
}

ｺﾞﾒﾝ｡

720 ：名無しさん＠３周年：02/08/09 20:12 ID:DVY9rXki

素数判定と同時に因数分解するのって　エラトステネスくらいじゃなかたっけ？

721 ：名無しさん＠３周年：02/08/09 20:12 ID:/dUSyDM6

>>694
この本に出てきたからおいらは知ってた。オススメ。
http://shopping.yahoo.co.jp/shop?d=jb&id=30966259

722 ：名無しさん＠３周年：02/08/09 20:13 ID:uVOxiLkL

>>719
く、苦しい。ちょっと利口なコンパイラなら確実に展開したコードを
吐き出しそう。

でも、いいたいとはよく分かりましたです。ありがとうでした。

723 ：つくばセンター ◆Oky6/ASA ：02/08/09 20:13 ID:+XTVyrTg

生物屋なんで数学はさっぱり理解できないが、
以外に論文のページ数が少ないのには驚いた。

有名なワトソン＆クリックの「A structure for Deoxyribose Nucleic Acid」
の論文も、わずか数ページだったらしいからなぁ。

そんなものなのかもしれん。

724 ：名無しさん＠３周年：02/08/09 20:15 ID:6OlkANtt

>>719
なんかちがうぞ（ｗ

725 ：名無しさん＠３周年：02/08/09 20:17 ID:6OlkANtt

>>721
全然関係ないように見えますが。・。・。・

726 ：.：02/08/09 20:17 ID:zCAt2d0/

恒河沙
阿僧祇
那由他
不可思議
無量大数

727 ：名無しさん＠３周年：02/08/09 20:21 ID:ZaG9Gsoo

プロキシか

728 ：名無しさん＠３周年：02/08/09 20:22 ID:mcn14OWo

無量大数まで暗記したのがちっちゃいころの自慢でした

729 ：７２４：02/08/09 20:23 ID:6OlkANtt

>>719
ごめん。おもしろいね

730 ：名無しさん＠３周年：02/08/09 20:24 ID:X1cA8g2Y

>728
小さい方は？

731 ：ていうか ◆16H8/cmo ：02/08/09 20:24 ID:T3ys6CfN

>>718 さんくす

何となくイメージは湧いたような・・・

732 ：名無しさん＠３周年：02/08/09 20:28 ID:mcn14OWo

>>730
小さいほうは覚えようとした記憶が少しある･･･
ふん
りん
もう
し
ﾜｽﾚﾀ

733 ：名無しさん＠３周年：02/08/09 20:28 ID:KvJXvnDb

山口人生に知らせろ。

734 ：???H：02/08/09 20:29 ID:X5BHtjfC

つくばセンター ◆Oky6/ASA ：よ、カイコ研やけど知ってるか？
********************************************
女子高生に痴漢、つくばの研究員逮捕
高速バスの車内で胸にひじを押し付ける

　埼玉県警吉川署は８日、高速バスの車内で痴漢をしたとして東京都迷惑防止条例違反の現行犯で、茨城県つくば市竹園、農業生物資源研究所（つくば市）の研究員安河内祐二容疑者（３４）を逮捕した。

　調べでは、安河内容疑者は８日午後９時１５分ごろ、東京都足立区の首都高速６号を走行中の東京発つくば行きＪＲ高速バスの車内で、隣に座っていた茨城県内の県立高校２年の女子生徒の胸にひじを押し付けるなどした疑い。同容疑者は容疑を否認している。

　女子生徒が別の乗客に助けを求めたため、運転手が埼玉県三郷市の常磐自動車道三郷料金所でバスを止めて１１０番。吉川署員が逮捕した。

　同研究所は農水省所管の独立行政法人。

ZAKZAK 2002/08/09

------------------------------------------------------------------------

735 ：　：02/08/09 20:32 ID:cX05mBYI

>730 見るべし
http://www.nobi.or.jp/i/kotoba/kanji/figure/kanji.html

736 ：名無しさん＠３周年：02/08/09 20:34 ID:GhI/5AL+

今だに語り継がれる
「コスモス」と日本ＩＢＭのＣＭは偉大だったんだなーと思う。

737 ：名無しさん＠３周年：02/08/09 20:35 ID:jPBjbZkN

インド人はすぐには金にならないことにも熱中できる。
中国人はすぐに金になることに熱中する。
この違いだなあ。

738 ：つくばセンター ◆Oky6/ASA ：02/08/09 20:37 ID:+XTVyrTg

>>734

東京出るのに、そのバス利用するが・・・なんとまぁ～（；´Д｀）
まぁ、つくばの研究所勤めは出会いが無いので、
思わず、手が出てしまったのだろう・・・と、同情してみたり。

漏れも気をつけねば･･･

739 ：　　：02/08/09 20:38 ID:cX05mBYI

>737
現代は確かにそうだと思う。
しかし、古代は別にそうではないと思う。

740 ：つくば原人：02/08/09 20:42 ID:GFpyNpUY

>>734
！！！！

741 ：名無しさん＠３周年：02/08/09 20:42 ID:X1cA8g2Y

>>735
おお、サンクス。
最小単位「浄＝１０の―２３乗」は意外に大きいね。プランク定数くらいは余裕で行くかとおもた。

742 ：名無しさん＠３周年：02/08/09 20:44 ID:IBmIWJqf

>>678
力技の実装

743 ：名無しさん＠３周年：02/08/09 20:45 ID:mcn14OWo

瞬息(ｼｭﾝｿｸ)
刹那(ｾﾂﾅ)

あたりはカッコよさげな名前。

744 ：名無しさん＠３周年：02/08/09 20:55 ID:zdzoP67S

P とか NPって何じゃ～～

745 ：名無しさん＠３周年：02/08/09 20:56 ID:8E+cRxUA

これによって今の時間も、ばしばし暗号が解読されてるわけ！？

746 ：名無しさん＠３周年：02/08/09 20:59 ID:X1cA8g2Y

>744
大雑把に説明すると、
P＝高速コンピューターでしらみつぶしに調べれば解ける問題
NP＝それでも解けない問題

747 ：名無しさん＠３周年：02/08/09 21:00 ID:TOcDEJ+S

>>744
山口人生先生にきいてみるよろし
http://www.3-i.info/top.htm

748 ：名無しさん＠３周年：02/08/09 21:01 ID:MvDAwTqi

>>744
誤解を恐れずに言うと、
P＝パンチラ
NP＝ノーパン

749 ：名無しさん＠３周年：02/08/09 21:03 ID:TOcDEJ+S

>>748
ある意味正解かも

750 ：名無しさん＠３周年：02/08/09 21:04 ID:6OlkANtt

>>748
warat

751 ：名無しさん＠３周年：02/08/09 21:14 ID:XwJEk3QO

>>748
君はたった今、Ｐ≠ＮＰを証明した！！！

752 ：名無しさん＠３周年：02/08/09 21:16 ID:PF4qc64k

よく分からんのだけど、
素数かどうかを短時間で判定することってそんなに大変なの？

753 ：名無しさん＠３周年：02/08/09 21:17 ID:555eRxOk

>>752
桁が多くなるほど大変

754 ：名無しさん＠３周年：02/08/09 21:18 ID:ik/+tUAh

インド人はたぶん、何十種類もあるスパイスの組み合わせを考えているうちに、
数学が得意になったんだろう。

755 ：名無しさん＠３周年：02/08/09 21:18 ID:XrS1MVNL

>素数判定を多項式時間(polynomial time)で可能なアルゴリズム

これを理解できない者は暗号も解けない。
世の中、天才はごくわずか。よって心配無用。

756 ：名無しさん＠３周年：02/08/09 21:20 ID:jSXndPJR

>>755
解読ツールが出回ったら終わりだろ

757 ：名無しさん＠３周年：02/08/09 21:21 ID:yy3NBQ3u

>>755
>>194

758 ：広末涼子(本物) ◆FAKE/J5A ：02/08/09 21:21 ID:z07QHZyf

>>752
やってみれば解るよ。

759 ：名無しさん＠３周年：02/08/09 21:22 ID:iUd3W1+P

インド人は、なんと２桁の九九ができるらしい。
それも全員。
これからは中国よりインドだ！
日本も３桁までやれ！

760 ：名無しさん＠３周年：02/08/09 21:23 ID:HeI4SU12

日本って研究開発とか科学とか数学の分野の記事が
全然注目されない国なのに結構スレが伸びててﾋﾞｸﾘ

761 ：名無しさん＠３周年：02/08/09 21:24 ID:wCqEnPma

誰かＣでソース書いてないの？

762 ：名無しさん＠３周年：02/08/09 21:25 ID:LIdaI3Qq

インド人は生命力が伊達じゃない。
インドは特別、マジで。

763 ：名無しさん＠３周年：02/08/09 21:25 ID:gFh3NMg8

判定問題と探索（素因数分解）問題は普通難しさが違うヨ

764 ：名無しさん＠３周年：02/08/09 21:26 ID:3VUT7Q2T

>>761
ム板にｶﾓ～ﾝ

765 ：名無しさん＠３周年：02/08/09 21:27 ID:WjCEIXiw

>>761
ム板でやっとる。
http://pc3.2ch.net/tech/

766 ：名無しさん：02/08/09 21:29 ID:ol+7Mf3M

>>760　科学が注目されないんじゃなくて、報道する側が
取り上げない（自分達に難しいから）、取り上げても、
その伝え方が上手くない、って感じ。

767 ：名無しさん＠３周年：02/08/09 21:33 ID:QrX08uF7

あ、これは偉いね。

768 ：反省汁！ ◆9d/c1mMc ：02/08/09 21:36 ID:ko+9iltN

漏れは、何も役に立たない文系人間だとこのスレを思って感じた。
インド人は凄い・・・数学とカレーの偉大なる国だ。

最近、この本を読んだ
http://www.amazon.co.jp/exec/obidos/ASIN/4167651025/250-7244121-0193808
ここに素数の仕組やＳＳＬのことに触れていた。
が、これがセキュリティー問題に直結するのかすら、理解できない。

うーん、役立たずだなぁ・・・

769 ：名無しさん＠３周年：02/08/09 21:36 ID:MzTeK2fo

>>607の補足をしておきます。

まず、二項定理というものがあります。

(a+b)^n = ∑(n!/((n-k)!*k!))*a^k*b^(n-k)

ゆえに、nが素数であるならば、a^n と b^n 以外の係数は必ずnで割り切れます。

この二項定理を用いて、フェルマーの小定理が証明できます。
フェルマーの小定理は、

pが素数のとき、pと互いに素な数aをとると、a^p をpで割った余りは a

です。

770 ：名無しさん＠３周年：02/08/09 21:38 ID:r3X1cuab

インド人は数学が得意なんだねえ。
すごい。

771 ：ていうか ◆16H8/cmo ：02/08/09 21:39 ID:T3ys6CfN

slashdot記事ﾊｹｰﾝ！
http://slashdot.org/articles/02/08/07/0151216.shtml

772 ：名無しさん＠３周年：02/08/09 21:39 ID:uvhLJ6BH

765894136515527は素数か？

773 ：769：02/08/09 21:40 ID:MzTeK2fo

あ、訂正

フェルマーの小定理

pが素数のとき、pと互いに素な自然数aをとると、a^(p-1)をpで割った余りは1

774 ：名無しさん＠３周年：02/08/09 21:42 ID:RsCeK1b2

インド人にびっくり。

775 ：名無しさん＠３周年：02/08/09 21:44 ID:6OlkANtt

>>769
pが素数でないときの定理もあったな。
オイラー関数つかうヤシ

776 ：名無しさん＠３周年：02/08/09 21:44 ID:/BJZy9il

なんとなく分かったふりでお茶を濁すスレはここですか？

777 ：名無しさん＠３周年：02/08/09 21:45 ID:LoniCHNr

>>773

何が言いたいのかな？おばかさん（ﾌﾟ

778 ：名無しさん＠３周年：02/08/09 21:46 ID:3Sd83cE2

例題) 2^11-1を素因数分解せよ

解答: 2^11-1 = 2047 = 23 * 89

以上を踏まえて…

問題) 2^71-1を素因数分解せよ

779 ：名無しさん＠３周年：02/08/09 21:46 ID:6OlkANtt

>>776
(´・ω・`)。むずかしくてよくわからないぽ。
>>777
( ´,_ゝ`)ﾌﾟ

780 ：名無しさん＠３周年：02/08/09 21:47 ID:3Sd83cE2

>>772は素数

781 ：名無しさん＠３周年：02/08/09 21:47 ID:SbSXgcSR

インド人必死だな( w

782 ：名無しさん＠３周年：02/08/09 21:48 ID:6OlkANtt

>>781ﾜﾗﾀ

783 ：名無しさん＠３周年：02/08/09 21:49 ID:uvhLJ6BH

>>780
正解。自作素数表作成ソフトにて生成。範囲指定できるから結構速かった。

784 ：名無しさん＠３周年：02/08/09 21:50 ID:+uNsT0Il

>>776は素人

785 ：名無しさん＠３周年：02/08/09 21:50 ID:N/d1C085

>772 は偶然入力した数だとしたらすごい。
>778 228479 × 48544121 × 212885833
このくらいなら素数表を持っていてしらみつぶしが速いかも。

素因数分解が多項式時間でできるのかと思って興奮してしまったが、
素数判定なんだね。それでも重要な結果だけど。

786 ：名無しさん＠３周年：02/08/09 21:51 ID:3Sd83cE2

>>783
それでは>>778をよろしく。

787 ：名無しさん＠３周年：02/08/09 21:51 ID:3Sd83cE2

鬱だ氏のう

788 ：名無しさん＠３周年：02/08/09 21:51 ID:zo29aPmt

>>773
訂正もなにも、どちらも正しいフェルマーの小定理だよ。

789 ：2.718@インド帰り：02/08/09 21:52 ID:6Qf7Nffu

>>781
マジでそうだからあんまり笑えないよ

790 ：773：02/08/09 21:52 ID:MzTeK2fo

>>777
a < p の場合は >>769 の表現でもよいが、そうでない場合もありますので。

>>607 にあるように、本件ではa<pの場合しか用いないので>>769 のままでもよいのですけどね。

791 ：2.718：02/08/09 21:55 ID:6Qf7Nffu

>>790
結局もぢゅろでどーのこうのの話だからどっちでもいいじゃん

792 ：785：02/08/09 21:56 ID:N/d1C085

素数定理によれば、
x あたりの自然数は ln x 個に1個程度が素数なので、
2^71-1 くらいでも 3% 弱は素数なんですね。

793 ：名無しさん＠３周年：02/08/09 21:56 ID:3Sd83cE2

adlemanの素数判定より速ければ応用がいろいろ効きそうだけど

794 ：名無しさん＠３周年：02/08/09 21:57 ID:wjpbKSrU

インドの数学は偉大だ

795 ：名無しさん＠３周年：02/08/09 21:58 ID:+uNsT0Il

何でインドでは数学が発達したの？

796 ：752：02/08/09 21:59 ID:PF4qc64k

>758
判定するための方法を考えてみますた。
以外に簡単に分かるような。。。

素数を理解してないだけかな（；´Д｀）

797 ：名無しさん＠３周年：02/08/09 21:59 ID:N/d1C085

>793
十分大きい数に関しては速いのだろうけど、
それが 1000桁からなのか、1兆桁からなのかが重要ですね。

798 ：名無しさん＠３周年：02/08/09 21:59 ID:Z42G3eIm

>>795
金持ち層（バラモン）は仕事にわずらわされることなく、数学に没頭することが
許されるから。

799 ：名無しさん＠３周年：02/08/09 22:00 ID:FdyC43ge

結局まとめると
「今までは確率的多項式時間実行可能な素数判定アルゴリズムしか
提案されてなかったが、
今回、多項式時間実行可能なアルゴリズムが提案されました。
これで、RSAなど、鍵を生成するために非常に大きな数の素数判定が
必要な公開鍵暗号では鍵の生成の効率が若干良くなります。」
これでOK?

800 ：2.718：02/08/09 22:00 ID:6Qf7Nffu

>>792
素数定理の収束って結構遅い（ついでに全然単調じゃない）んじゃなかったっけ？
2^71程度でx/ln(x)で近似できるのかな？

801 ：名無しさん＠３周年：02/08/09 22:01 ID:+uNsT0Il

>>798
ほーそうなんだ

802 ：名無しさん＠３周年：02/08/09 22:01 ID:vLwuJnr6

生物学と素数も密接に関係してるぞ＞生物屋

ジュウシチネンゼミとかジュウサンネンゼミが面白い
17、13年間、土の中ですごして2，3週間で繁殖するってサイクルを繰り返すセミ
なんだけど、セミに寄生する寄生虫の寿命とうまくかぶらないように進化した
っていう説がある。寄生虫の寿命がが2年だとすると16以下の数では
決して、セミと寄生虫が出会うことはない。
17、13の倍数の寿命をもった寄生虫しかセミに寄生できない。
寄生虫の寿命が1年サイクルだとその間に寄生できるセミがいないってことになって
寄生虫の方がほろんじゃうしね。

普通のセミの寿命も7年とかだったかな？

803 ：名無しさん＠３周年：02/08/09 22:02 ID:Z1iW4qTp

実はインドは小さい頃から暗記教育がすさまじい。
幼稚園のころには神様の名前を1000以上覚えさせられるんだって。

804 ：名無しさん＠３周年：02/08/09 22:03 ID:8x0TG2jZ

ＲＳＡを解読するには、死ぬほど早い剰余計算ができればＯＫで、
基本的には、公開鍵 e, N から、秘密鍵 d は求まる。

e ^ (-1) mod ((p-1)(q-1))

は、拡張ユークリッド互助法で一瞬で求まるので、要は、

N % i == 0 となるような、 i を見つけられればＯＫ。RSAの公開鍵Nは、
大きな２つの素数の積なので、そういう i はNを作るときの２つの素数
以外にありえない。

　２つの素数の積を因数分解で求めることが困難なことが、ＲＳＡ暗号
の解読が難しい根拠になっている。

int p, q;
for ( i = 3 ; i < N ; i+= 2 ) {
if ((N % i) ==0) {
p = i;
q = N / p;
d = e^(-1) mod((p-1)(q-1))
return d;
}
}

805 ： ◆MUMUMU4w ＠むむむφ ★：02/08/09 22:05 ID:???

今家に着いた。800超えてる、、、。

/. Japanにも記事出ましたね。
http://slashdot.jp/article.pl?sid=02/08/09/1248255&mode=thread

806 ：　：02/08/09 22:06 ID:9OCoGkJ0

インドで教育受けてる人って4億くらいだよな。
日本と比べるとたかが４倍なのに天才の発生率は４倍どころじゃないよな。
やっぱ民族的にあるんだなそーゆうの。

807 ：名無しさん＠３周年：02/08/09 22:07 ID:8x0TG2jZ

>>82
バーナム暗号って、ただの xor だから関係ない罠。
ついでに、ＡＥＳとかもまったく関係なしです。

808 ：名無しさん＠３周年：02/08/09 22:08 ID:Cq7Xv/WK

>>800
2^71ってーと、大体10^21か。そのくらいだと多分まともな近似には
なってないと思われ。

809 ：名無しさん＠３周年：02/08/09 22:09 ID:jrZKGxr0

>>799
全然違うよ。

RSAなどの暗号強度は、ある数の素因数分解におそろしく時間がかかる
ことを利用している。このアルゴリズムは、確率論ではなくて決定的な
アルゴリズムであることから明らかなように、素数判定が短時間でできる
ということは、素数でなければ素因数分解も短時間でできるということだ。
論文４ページのアルゴリズムのところに「output COMPOSITE」とある
ことからも、そのことは明らかだろう。

アルゴリズムが明らかになってしまった以上、RSAやぶりのソフトが
出回るのも時間の問題と思われ。

810 ：名無しさん＠３周年：02/08/09 22:09 ID:0DzdLY/Q

>>806
日本は天才の才能を伸ばしてやれるような制度になってないじゃん。

811 ：名無しさん＠３周年：02/08/09 22:09 ID:vLwuJnr6

>>806
日本じゃ論文の数より寝た女の数の方が世間に認められるからな

812 ：名無しさん＠３周年：02/08/09 22:09 ID:8x0TG2jZ

>>77
ＲＳＡの高速演算法として中国人剰余定理はよくもちいられていまふ。
中国人とどういうかんけいにあるのかよくわからないけど。

813 ：名無しさん＠３周年：02/08/09 22:10 ID:kRX6mQUw

>>803
>幼稚園のころには神様の名前を1000以上覚えさせられるんだって。
いくら、ヒンデゥー教でも神様1000人は多すぎでは…

814 ：名無しさん＠３周年：02/08/09 22:11 ID:Cq7Xv/WK

>>809
嘘を書くな、嘘を。

＞ということは、素数でなければ素因数分解も短時間でできるということだ。

これは明らかな間違い。

＞「output COMPOSITE」

これは「nが合成数である事という出力を行う」という意味

815 ：名無しさん＠３周年：02/08/09 22:13 ID:wUKrwUq3

>>809
＞素数判定が短時間でできる
＞ということは、素数でなければ素因数分解も短時間でできるということだ。
このスレではそうではないと何度も議論されているのだけれどね。

816 ：名無しさん＠３周年：02/08/09 22:13 ID:Cq7Xv/WK

>>812
古代中国の暦の研究に中国式剰余定理の特別な場合が
使われてたからこう呼ばれるらしい。

817 ：799：02/08/09 22:14 ID:FdyC43ge

>>814,815
ということは、７９９のまとめで正解？

818 ：名無しさん＠３周年：02/08/09 22:15 ID:Cq7Xv/WK

>>817
間違いないかと。

819 ：2.718：02/08/09 22:16 ID:6Qf7Nffu

>>817
ですね。

820 ： ◆gaChapSQ ：02/08/09 22:17 ID:QhPpPP7Y

やばいです。
本気でやばいです。
RSA暗号の危機でがんす

821 ：名無しさん＠３周年：02/08/09 22:17 ID:wcdd5+T8

数学板じゃ怒られたから、こっちに書くけど、
素数の性質ってその数と１以外で割る事が出来ない。
これだけじゃないの？それ以外の性質を利用してるの？
ある数が合成数だと判断できたけど、どんな数から合成されたか
分からないって言われても。なんか信じられない。

822 ：名無しさん＠３周年：02/08/09 22:18 ID:/e2EofrJ

>>820

何で？

823 ：名無しさん＠３周年：02/08/09 22:18 ID:zo29aPmt

>>809
おいおいこのアルゴリズムでは
合成数だと判定できても素因子はわからないよ。

824 ： ◆gaChapSQ ：02/08/09 22:18 ID:QhPpPP7Y

>>822
・・ごめん、レス読んでなかったっす

825 ：（　゜д゜）ｳﾏｰ ◆UMAAVF96 ：02/08/09 22:19 ID:6hhi9oZd

ゴルゴ13にもこういう話し合ったよな。日本人の数学者がすべての暗号を無効化する公式を発見するやつ

826 ：名無しさん＠３周年：02/08/09 22:19 ID:wcdd5+T8

>>823
何で合成数と判断できるの？眠れないから教えてよ--。
ちょっと難しくても良いから。

827 ：2.718：02/08/09 22:20 ID:6Qf7Nffu

ところで、十分な素数表が用意されたとして、それでも素因数分解って
難しいのかな？

828 ：名無しさん＠３周年：02/08/09 22:20 ID:mIXS5ZK8

ゴマキが卒業したのも、
TMRevolutionが離婚したのも、
俺の仕業

829 ：名無しさん＠３周年：02/08/09 22:20 ID:5xfoNO1P

まさかこんだけ盛り上がるとは・・・・・

830 ：名無しさん＠３周年：02/08/09 22:21 ID:3Sd83cE2

>>821
数学をもっと勉強しましょう。

831 ：名無しさん＠３周年：02/08/09 22:21 ID:wUKrwUq3

>>820
やばくない
ＲＳＡの危機ではない

832 ： ◆gaChapSQ ：02/08/09 22:21 ID:QhPpPP7Y

数学への理解が深いってーのは、
羨ましいよなー・・・
・・・・勉強もっとキチンとしてれば良かったよ。ｸﾞｯｽｼ。

833 ：名無しさん＠３周年：02/08/09 22:21 ID:t8kjoB2P

100桁200桁の素数表用意するのが難しいかと。。>>827

834 ：名無しさん＠３周年：02/08/09 22:21 ID:zo29aPmt

>>821
nが素数だと(x-1)^nの1次からn-1次の係数はすべてnで割り切れます。
(x-1)^4=x^4-4x^3+6x^2-4x+1の2次の係数は6で4で割りきれないから
4は素数でないと判定できます。
しかし、４の素因子は何かはこの判定法からはわかりません。

835 ：名無しさん＠３周年：02/08/09 22:22 ID:wUKrwUq3

>>827
素数表ってどういうの？

836 ：名無しさん＠３周年：02/08/09 22:23 ID:3Sd83cE2

>>827
素数表で素因数分解をするには、対象となる値nの平方根以下の全ての素数が
必要。

つまり、例えば(10^100+267)の素因数分解を素数表のみで行うには、10^10以下
の全ての素数表を用いて、その全ての数で割ってみないと分からないということ。

837 ：名無しさん＠３周年：02/08/09 22:23 ID:wcdd5+T8

>>830
頼むよー。今回のこのアルゴリズムで使ってる、素数の性質だけで良いカラさぁ。
教えてくれよー意地悪するなよー。

838 ：名無しさん＠３周年：02/08/09 22:23 ID:Cq7Xv/WK

>>827
N以下の素数は大体 N*log(N) 個（素数定理）。
つーことで、Nの桁数の指数オーダー個の数について
除算を実行する事になるので困難でつ。

839 ：名無しさん＠３周年：02/08/09 22:24 ID:2cJtrVHT

インド人嘘つかない

840 ：名無しさん＠３周年：02/08/09 22:24 ID:zo29aPmt

>>827
桁数が大きくなると素数表の素数の数が全宇宙の素粒子の個数を超えるはず。
よって素数表を十分用意するわけにもいかない。

841 ：名無しさん＠３周年：02/08/09 22:24 ID:40HbmcwW

スレとはあんまし関係ないけど、

∫√(1+t^2)dt

って
t=sinhθ
って置換するのが簡単そうだけど学校ではついに習わなかったな。

842 ：名無しさん＠３周年：02/08/09 22:25 ID:yy3NBQ3u

>>837
オイラーの小定理から勉強すれ

843 ：名無しさん＠３周年：02/08/09 22:25 ID:wizU8UYy

>>836
よくわからないので数学板へ逝ってきます・・・

844 ：名無しさん＠３周年：02/08/09 22:25 ID:zo29aPmt

>>837
>>834にかいてあるよ。

845 ：名無しさん＠３周年：02/08/09 22:25 ID:GwMISYK2

こっちのほうが凄い。

【ノーベル賞確定？】数学法則発見！！【大発見】
http://science.2ch.net/test/read.cgi/math/1026398334/

846 ：名無しさん＠３周年：02/08/09 22:25 ID:wUKrwUq3

。まあ、素数判定が早くできるからって素因数分解が早くできるわけでもないということ。
ＲＳＡはまだ安泰だわな。

847 ：842：02/08/09 22:26 ID:yy3NBQ3u

フェルマーだった

848 ：名無しさん＠３周年：02/08/09 22:26 ID:EXHBVH2R

正直、なにがなにやらさっぱり。
こーゆーとき、理系をうらやましく思うよ。

849 ：名無しさん＠３周年：02/08/09 22:26 ID:wcdd5+T8

>>834
おぉありがとう。そう言う事かぁ。

850 ：名無しさん＠３周年：02/08/09 22:28 ID:vLwuJnr6

>>847
オイラーの定理はフェルマーの定理の一般化されたやつだから間違いではない

851 ：名無しさん＠３周年：02/08/09 22:28 ID:FdyC43ge

◆MUMUMU4w ＠むむむφ ★ の謝罪文はまだ？

852 ：名無しさん＠３周年：02/08/09 22:28 ID:wUKrwUq3

>>845
ＷＯＲＤで読むのメンドクセー
要約しろ

853 ：名無しさん＠３周年：02/08/09 22:29 ID:xrt115iG

もしや？とおもたらやっぱインド工科大か。
ここの入試問題って大学院並みでニッポンの暗記数学じゃ歯が立たん
らしい。
東京出版の学コン常連がアカンかったそうじゃ。だれか知ってるﾔｼ、
カキコしてけろ。

854 ：名無しさん＠３周年：02/08/09 22:30 ID:wUKrwUq3

>>849
スゲー、わかったのか？

855 ：名無しさん＠３周年：02/08/09 22:31 ID:8x0TG2jZ

>>827
いま、RSAで用いられている素数は、512ビットです。
512ビットの素数は、少なく見積もっても2^500個以上
はあるはずなので、その表を用いていちいち割り算
することを考えると、因数分解はまだまだ難しいと
おもわれまふ。

856 ：名無しさん＠３周年：02/08/09 22:31 ID:boTTAKMa

素数表を素数の性質を利用して圧縮（少ないテーブルの組み合わせから目的の桁まで生成できる）
できればRSAってもう少し簡単に解けそうな気がするんですが

857 ： ◆gaChapSQ ：02/08/09 22:32 ID:QhPpPP7Y

RSA暗号について、
（　SFマガジン7月号P５１より　）
まず、大きな数字を二つ見つけておきます。
それを　ｐ　と　ｑ　とします。
これを掛けて出来る巨大な整数を　N　としましょう。
　N＝ｐｑ　であります。
さらに、２つの整数　ｒ　と　ｓ　で、その積ｒｓを
（ｐ－１）（ｑ－１）で割ると１余るようなものを見つけておきます。

暗号受信者は、整数　N　と整数　ｒ　だけを公開しておきます。
これは、暗号発信者だけでなく一般公開しても差し支えないです。
その上で、　ｐ　と　ｑ　と　ｓ　は秘密にしておきます。
　　　　　　　　　　　　　（　省略　）
暗号化したい文章を自然な方法で数字に直します。
Sの数字を　ｘ　としましょう。　ｘ　は巨大な整数です。
次に　ｘ　を　ｒ　乗してそれを　N　で割った余りを求めます。それを　ｒ　としましょう。
この　ｙ　が暗号化した文章なのです。
　　　　　　　　　　　　　（　省略　）
秘密の整数　ｓ　で　ｙ　を　ｓ　乗して　N　で割った余り求めると元の数字　ｘ　に戻るわけであります。

858 ：名無しさん＠３周年：02/08/09 22:33 ID:zo29aPmt

>>837さんへ
>>607 >>625 >>834 を読んでみてください
すこし改定
---
xの3乗をx^3と書きますね。

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

nを与えられたらnと互いに素な数aを取って
多項式(x-a)^nの1次から(n-1)次までの係数がすべてnで割り切れて
a^nをnで割った余りがaならばnは素数である。

でもこのやりかたではn次の多項式の係数を計算しなければならず大変
よって小さい数rをうまくとって
x^rは1とする計算を間に入れてr次の多項式の計算に収めればよい。
このrの候補の取り方が最初のwhile文。
このrは小さい数ですむというのがLemma4.2の主張。
チェックaの候補もrが小さいので少しの候補ですむ。

r次以下の多項式(x-a)^nの係数の計算はFFT高速乗算法を使えばよいのだろう。

8ページ目には予想として、この判定は
このaは1だけのチェックでよく、
rはnの約数でもなくn^2-1の約数でもないという条件だけでよいのではないか
といっている。

859 ：名無しさん＠３周年：02/08/09 22:33 ID:boTTAKMa

それにRSA暗号って署名なんかに使われるわけで
データ本体の暗号化はRC4なんかが多いんだよね。

860 ：（　゜д゜）ｳﾏｰ ◆UMAAVF96 ：02/08/09 22:34 ID:6hhi9oZd

>>857
なるほど、そういうことか

861 ：名無しさん＠３周年：02/08/09 22:34 ID:PRHJaZTh

おいおい、途中を省略したらいかんだろ。（笑）

862 ：名無しさん＠３周年：02/08/09 22:35 ID:Cq7Xv/WK

>>859
暗号化・復号化が遅いから、長文のやりとりには向かないよね。

863 ：名無しさん＠３周年：02/08/09 22:35 ID:kRX6mQUw

>>859
秘密鍵式暗号の方が高速なので、鍵をランダムに生成してデータ本体はそれで暗号化。
鍵をRSAなどの公開鍵暗号で暗号化して添付して送る。
といった使い方はメジャーなので、RSAが破られると被害甚大であるのはたしか。
NSA辺りには、今は解けないけれど、将来是非解読したい暗号メールが山ほど保存してあるんだろうな…

864 ：　　：02/08/09 22:37 ID:bubLDLpJ

なぞじゃむ使えば問題ねーだろ。

865 ：名無しさん＠３周年：02/08/09 22:37 ID:wcdd5+T8

>>854
うん。
ただし定理の証明すら理解できないほど馬鹿だけどね。知ってた。
馬鹿理系ってこんなものさ。(´･ω･`)ショボン

866 ：名無しさん＠３周年：02/08/09 22:37 ID:8x0TG2jZ

>>836
10＾50以下のすべての素数表が必要な気が・・・・

867 ：：02/08/09 22:37 ID:3Q0s14/e

山口人生
「Ｐ＝ＮＰ？」問題の解決
http://www.3-i.info/news1.htm

868 ：名無しさん＠３周年：02/08/09 22:37 ID:wUKrwUq3

「そういうことか」
と言ってる奴って本当にわかってるのかな　ｗ

869 ：2.718：02/08/09 22:37 ID:6Qf7Nffu

>>836他の方々
やっぱり、因数分解は実質総当り（適当な間引きはかなりできるだろうけど）なのか…
そりゃRSA安泰だわな…とオーダーだけを根拠に納得。
素数表を用意するという仮定に無理があったか。

>>838
ちなみにだいたいN/ln(N) 個だよ

870 ：名無しさん＠３周年：02/08/09 22:38 ID:MzTeK2fo

ちなみに、RSA暗号の強度は「巨大な数の素因数分解が難しい」という性質よりは、
むしろ「剰余計算は逆算することが難しい」という性質に依存してます。

871 ：名無しさん＠３周年：02/08/09 22:38 ID:3Sd83cE2

>>866
入力ミスった鬱だ二度と来ません…

872 ： ◆gaChapSQ ：02/08/09 22:39 ID:QhPpPP7Y

たしか、記憶が確かなら、
RSA暗号の当初に総当り式で素因数分解をコンピータにさせたら、
１５年ぐらいかかったって話ですが・・・

873 ：名無しさん＠３周年：02/08/09 22:39 ID:boTTAKMa

暗号強度はキーが何ビットかが重要

874 ：名無しさん＠３周年：02/08/09 22:39 ID:wUKrwUq3

>>863
秘密鍵暗号の鍵が知られてしまうのは困るね。
でもＲＳＡはまだ十分強固だ。

875 ： ◆gaChapSQ ：02/08/09 22:40 ID:QhPpPP7Y

とにかく、みなさん！！
ニール・スティーブンソン　『クリプトノミコン』
を読みましょう♥

876 ：名無しさん＠３周年：02/08/09 22:41 ID:kXI9VqA1

？？？？？

877 ：名無しさん＠３周年：02/08/09 22:41 ID:Cq7Xv/WK

>>869
ゴメソ。ただのタイプミス。N*log(N)じゃNより大きいわな（ｗ

ln については、暗号やってると log_10 を log って書いちゃう癖が
つくんだと少しだけ言い訳。

878 ：名無しさん＠３周年：02/08/09 22:42 ID:kXI9VqA1

？？？？？

879 ：名無しさん＠３周年：02/08/09 22:42 ID:fShpN5pA

インド人はなにげに頭ｲｲ

880 ：名無しさん＠３周年：02/08/09 22:43 ID:3Sd83cE2

× インド人は頭がいい
○ インド人は人口が多い

881 ：名無しさん＠３周年：02/08/09 22:43 ID:Cq7Xv/WK

>>870
「合成数を法とする」剰余計算の困難さな。

で、合成数を法とする剰余計算は結局その合成数を
素因数分解する事につながってるわけで、どっちも
同じ事と言っても良いでせう。

882 ：名無しさん＠３周年：02/08/09 22:44 ID:hVOjIqYQ

ちなみにＭＩＳＴＹはどんなレベルなの？

883 ：名無しさん＠３周年：02/08/09 22:44 ID:NTLMAw/+

RSA512ビットは危険。楕円DHかなんかで、そのくらいに相当する困難性のものがやぶられている。
初期のRSAはとっくに破られた。128ビットだったかな

884 ：名無しさん＠３周年：02/08/09 22:45 ID:sBhBJuwk

>>880

×東京はかわいい娘が多い
○東京は人口が多い

ってのと一緒か？

885 ：名無しさん＠３周年：02/08/09 22:45 ID:boTTAKMa

つーか、RSAは暗号としてはもう時代遅れ

886 ：2.718：02/08/09 22:45 ID:6Qf7Nffu

>>870
そうだけど、ほとんど因数分解と思っている漏れはブァカ？

887 ： ◆gaChapSQ ：02/08/09 22:45 ID:QhPpPP7Y

>>885
( ゜Д゜）ハァ？

888 ：名無しさん＠３周年：02/08/09 22:46 ID:wUKrwUq3

>>872
何ビットの場合かな？
ＲＳＡは１２８ビットだっけ。
分散処理ができるようになったら世界中のコンピュータのＣＰＵパワーを
利用して・・・・・
でも難しいかな？

889 ：　：02/08/09 22:46 ID:3Q0s14/e

>>879

数字の概念はインドで発達していて
日本の九十九の10進を16進以上で教えていたりする。

890 ：名無しさん＠３周年：02/08/09 22:47 ID:wUKrwUq3

>>882
ＣＰＵパワーが上がったせいじゃないの？

891 ：名無しさん＠３周年：02/08/09 22:48 ID:Cq7Xv/WK

>>872
RSAの安全性を知らしめるために、巨大な合成数を素因数分解させた話かな？
だとしたら、総当たりじゃなくてもっと効率の良いアルゴリズムを用いてると思う。
ちょっと記憶が曖昧なので間違ってたらｽﾏｿ。

892 ：2.718：02/08/09 22:48 ID:6Qf7Nffu

白血病解析より素数解析…
盛り上がらないだろうな（ｗ

893 ： ◆gaChapSQ ：02/08/09 22:48 ID:QhPpPP7Y

>>888
しらん。忘れた。
初期のころ、ﾘｳﾞｧｽﾄだか、シャミアだか、アドルマンだかが、
検証用に大学のUNIXで実施してから・・・って話だったような？

894 ：名無しさん＠３周年：02/08/09 22:49 ID:pLahvTdi

よくわかんないので、馬鹿なぼくでもわかるように
説明してください.

↓　よろしこ

895 ： ◆gaChapSQ ：02/08/09 22:49 ID:QhPpPP7Y

>>891
あ、それだ。多分。

896 ：名無しさん＠３周年：02/08/09 22:49 ID:JgTEgFzB

インド人はＩＴに馴染みやすいな
日本人は・・・

897 ：名無しさん＠３周年：02/08/09 22:49 ID:8x0TG2jZ

>>883
そう。そんなわけで、いまは p, q がだいたい512ビット同士の
1024ビットあたりが安全だと考えられています。もうすこし
したら2048ビットも本気でひつようとされるかもかも。

898 ：名無しさん＠３周年：02/08/09 22:49 ID:vLwuJnr6

>>872
素因数分解は並列処理に適してるからSETIみたいに
分散処理を行うと15年もかからずやぶられる可能性が高いよ

http://distributed.net/
ここで参加してみるのもいいかもね
偶然自分の計算したブロックが当たってれば1000ドルくらいもらえるはず

899 ：名無しさん＠３周年：02/08/09 22:50 ID:wcdd5+T8

ＲＳＡで何時も疑問に思うのが、そんなでっかい素数表だれが何処に
持ってるの？てこと。１Ｍの素数表で65536個だよね。
この程度なら解けるし。もしかしてキー作る時に素数を生成してるの？
でも今回のも素数作成アルゴリズムじゃなくて判定アルゴリズだよね。

詳しい人教えて。

900 ： ◆gaChapSQ ：02/08/09 22:50 ID:QhPpPP7Y

>>894
RSAはここ　→>>857
今回の論文についてはここ？→>>858

すまん、数学の本格的なところはさっぱりっすよ

901 ：つくばセンター ◆Oky6/ASA ：02/08/09 22:50 ID:+XTVyrTg

量子コンピュータと組み合わせて、うまいこと出来ないか？

http://www.internetclub.ne.jp/EASY/20020514.html

902 ： ◆gaChapSQ ：02/08/09 22:51 ID:QhPpPP7Y

>>898
あっはっは。宝くじやね。

903 ：名無しさん＠３周年：02/08/09 22:51 ID:yy3NBQ3u

RSA暗号はこっち >>168

904 ：名無しさん＠３周年：02/08/09 22:51 ID:vLwuJnr6

>>882
MISTYは秘密鍵暗号

905 ：名無しさん＠３周年：02/08/09 22:52 ID:kRX6mQUw

>>899
ランダムに大きい数を作って、素数判定アルゴリズムで素数を探し出す。
今回のほど効率は良くないが、素数判定アルゴリズムは他にもある。

906 ：名無しさん＠３周年：02/08/09 22:52 ID:t8kjoB2P

>>899 そのたんびに、生成してると思う。
乱数で生成して素数判定にかけるといったところでしょうか。

907 ： ◆gaChapSQ ：02/08/09 22:53 ID:QhPpPP7Y

>>899
自分がハカージャパン辺りで読んだのでは、
ランダムさはキー作成の際に、
キーボードをバシャバシャたたいて作るんだったような？

908 ：名無しさん＠３周年：02/08/09 22:54 ID:GwMISYK2

そういうことか。つまりアレだ、インド人もビックリって言う結論だろ。

909 ： ◆gaChapSQ ：02/08/09 22:54 ID:QhPpPP7Y

>>908
２ちゃんねるらしいな。

910 ：名無しさん＠３周年：02/08/09 22:54 ID:vLwuJnr6

>>907
擬似乱数生成器ってのをつかうんだよ

911 ：名無しさん＠３周年：02/08/09 22:54 ID:wcdd5+T8

>>905
そんなに簡単に見つかるもんなんだ。
なるほど、なるほど。

912 ：名無しさん＠３周年：02/08/09 22:56 ID:3Sd83cE2

>>911
時間がかかってもよければ、100%(合成数だと)判定する方法は既にあるんだよ。

913 ：名無しさん＠３周年：02/08/09 22:56 ID:wcdd5+T8

わーい。みんな有難うね。
素数表からランダムに選択してると思ってた. (´･ω･`)賢くなりたい。

914 ：名無しさん＠３周年：02/08/09 22:57 ID:8x0TG2jZ

>>899
適当な乱数を作って、素数かどうか判定します。

判定により、「合成数である」という結果がでれば、それは１００％素数ではない
のですが、「合成数ではない」という判定結果がでても、実際には合成数である
可能性が０ではないので（擬素数）、判定を何度も繰り返して、合成数である可
能性を下げていく、という方法をとります。

915 ： ◆gaChapSQ ：02/08/09 22:57 ID:QhPpPP7Y

>>910
なんとか関数ってやつ？

916 ：名無しさん＠３周年：02/08/09 22:57 ID:xjkhN0iN

こんなスレが1,000逝くのか？
結構理数系の人多いのね

917 ：名無しさん＠３周年：02/08/09 22:58 ID:vLwuJnr6

>>912
素数判定アルゴリズムをつかって素数じゃなかったら合成数だわな

918 ：名無しさん＠３周年：02/08/09 23:01 ID:3Sd83cE2

ちなみに、この本は非常に参考になる。

http://www.esbooks.co.jp/bks.svl?start&CID=BKS503&shop_cd=1&qty=1&product_cd=30892796&pg_from=srh
素数の世界　その探索と発見共立出版
Paulo Ribenboim著　吾郷孝視訳編

919 ：名無しさん＠３周年：02/08/09 23:17 ID:DZHSGYzg

素数が無限にあるっていう証明だけど、ほんとうにあってるの？？

920 ：2.718：02/08/09 23:21 ID:6Qf7Nffu

どの証明？

N以下の素数の個数をa(N)とすると
a(N)/(N/ln(N)) -> 1 (N->∞)
のことかな？（ｗ

921 ：名無しさん＠３周年：02/08/09 23:23 ID:0LnXiQo7

エニグマ暗号機の復活を望む（ｗ

922 ：コピペ：02/08/09 23:26 ID:QhPpPP7Y

#!/usr/bin/perl-s
$f=$d?-1:1;$D=pack('C*',33. .86);$p=shift;
$p=~y/a-z/A-Z/;$U=~s/( . *)U$/U$1/;
$D=~s/U( . )/$1U;';($V=$U)=~s/U/V/g;
$p=~s/[A-Z]/$k=ord($&)-64,&e/eg;$k=0;
while(<>){y/a-z/A-Z;y/A-Z//dc;$o.=$_}$o.="X"
while length ($o)%5&&!$d;
$o=~s/.chr(($f*&e+ord($&)-13)%26+65)/eg;
$o=~s/X*$//if$d;$o;$o=~s/.{5}/$&/g;
print"$o|n";sub v{$v=ord(substr($D,$_{0}))-32;
$v>53?53:$v}
sub w{$D=~s/(.{$_{0})(.*)(.)/$2$1$3}}
sub e{eval"$U$V$V";$D=~s/(.*)([UV].*[UV])(.*)/$3$2$1/;
&w(&v(53));$k?(&w($k)):($c=&v(&v(0)),$c>52?&e:$c)}

923 ：2.718：02/08/09 23:36 ID:6Qf7Nffu

>>922
これ、何？

924 ：名無しさん＠３周年：02/08/09 23:41 ID:yy3NBQ3u

>>923
暗号文

925 ：名無しさん＠３周年：02/08/09 23:45 ID:MzTeK2fo

>>921
既にチューリングに破られました

926 ：名無しさん＠３周年：02/08/09 23:49 ID:sBhBJuwk

>>923
パール

927 ：名無しさん＠３周年：02/08/09 23:51 ID:N/d1C085

>800 >808
10^6 程度でも、せいぜい 1割のずれなので、見積りとしては悪くないかと。

100万番目の素数と 100万1000番目の素数の差は 16314 。 ln(10^6) = 16.56。
100億番目の素数と 100億1000番目の素数の差は 26130 。 ln(10^10) = 26.25。

>813
3億の神がいるんじゃなかったっけ。
http://www3.sympatico.ca/untangle/Hinduconcord.html ここに 100ほど。

あまり関係ないけど、インドの英語では極めてしばしば
10^5 を lakh, 10^7 を crore と書きます。
（問：10^9 は？）当然 hundred crore です。インドの人口はこれより少し多くなりました。
（じゃあ、10^11 は？） ten thousand crore 。
（すると、10^12 は？）もちろん lakh crore です。インドの国家予算はルピー表示でこの程度です。

928 ：名無しさん＠３周年：02/08/09 23:53 ID:JgTEgFzB

おまえらすげぇな！

929 ：名無しさん＠３周年：02/08/09 23:55 ID:N/d1C085

>919
素数が有限個で、p_1, p_2, ..., p_N だとしましょう。
X = p_1 × p_2 × … × p_N + 1
という数を考えます。

この数が素数なら、知っていた素数のどれよりも大きいので仮定に矛盾。
この数が素数でないなら、どんな素数でも割り切れないので仮定に矛盾。

結局、素数が有限個とした元の仮定が誤り。

　1 + 1/2 + 1/3 + …
=(1 + 1/2 + 1/4 + … )(1 + 1/3 + 1/9 + … )(1 + 1/5 + 1/25 + …)…
= 2 × 3/2 × 5/4 × …
を使ってもいいですね。

930 ：名無しさん＠３周年：02/08/09 23:57 ID:5XVWpNB6

素数判定がＰで因数分解がＮＰなら、「合理的な時間で完全な暗号が作れることになりますた。」
というとてもおめでたい発表だと思うのだが

931 ：コピペ：02/08/09 23:58 ID:QhPpPP7Y

２＾２２０３-1

932 ：名無しさん＠３周年：02/08/10 00:00 ID:oT9frU5S

>>929
素数が有限個しかないと2番目(と3番目)の値が有限になるのに
1番目の式の値が発散するから矛盾し、結局素数は無限にあることになる、
って事？
へー、そんな証明法もあるんだ。

933 ： ◆gaChapSQ ：02/08/10 00:01 ID:tw58AxOY

あんさー、∞って数字でしょ？
これって素数なん？

934 ：名無しさん＠３周年：02/08/10 00:02 ID:wTtpDcgb

∞は数字でも数でもありません。

935 ：名無しさん＠３周年：02/08/10 00:02 ID:vK7YfXU0

perlのソースって読み難い

936 ：名無しさん＠３周年：02/08/10 00:04 ID:QvgDIWKf

ｃにしてよ、誰か。
コピぺしてそのまま使えるやつきぼん

937 ：名無しさん＠３周年：02/08/10 00:04 ID:S5awIRN3

ブッチ神父

938 ：名無しさん＠３周年：02/08/10 00:04 ID:25N1APNm

このスレはなにげにすごいぞ

939 ： ◆gaChapSQ ：02/08/10 00:07 ID:tw58AxOY

>>934
ｻﾝｸｽ

940 ：名無しさん＠３周年：02/08/10 00:08 ID:xtNr5rnr

>>938
元記事を理解できない文系が質問し、理解できている理系が説明する、
を繰り返しているだけという罠

941 ：名無しさん＠３周年：02/08/10 00:16 ID:GE802hy9

超準解析では、無限大や無限小を普通の実数と同じように四則演算できるけどね…
あんまりはやってないね…

942 ：名無しさん＠３周年：02/08/10 00:17 ID:js5rPAIv

cのソースがなかなかうpされないところをみると、、、
誰も論文を理解できてないな。

ところで、基本的な疑問なのだが、log の底はe でいいのか？

943 ：名無しさん＠３周年：02/08/10 00:18 ID:z0pXEM2M

インド人数学者って整数論とか強そうなイメージだけど、
実際はどうなんでしょう？

944 ： ◆gaChapSQ ：02/08/10 00:20 ID:tw58AxOY

>>942
理解できる人なら、２ちゃんねるより有意義なことしてると思われ。

それに、>>922は素数判定ちがうよ。
暗号作成用のコードだって本に書いてあったの移しただけ。
アレトゥサとかいってたっけ・・・？

945 ：名無しさん＠３周年：02/08/10 00:23 ID:fhUHzC8/

俺を含めて「インド人もびっくり」って書いたやつは９人

946 ：名無しさん＠３周年：02/08/10 00:23 ID:+MBWiKKm

>>942
ビット長が問題になるから底は２

947 ：名無しさん＠３周年：02/08/10 00:24 ID:PyXwhC4K

>>942
プログラム板でやってるよ。

948 ：名無しさん＠３周年：02/08/10 00:25 ID:H12v4vWq

>>942
一行目から10行目が力技で動かすことになっていて
実用的に書けないから。
rが(log n)^6のオーダーだからといって無理やり素数判定しているし。
r-1の最大素因子qを求めるのも√rから2まで割って求めているし。
(log n)^12のオーダーであることを証明するためのアルゴリズムだから
1-10行目が雑。

12行目での高速乗算法をだれもかかないからプ板で引っかかっている。
12行目はこんな感じ
http://pc3.2ch.net/test/read.cgi/tech/1028877628/141

949 ：2.718：02/08/10 00:25 ID:j84wxqpX

>>942
論文の
4: The Algorithmの12
if ((x-a)^n != x^n -a (mod x^r - 1, n)) {
output COMPOSITE;
}

これをCで1からコーディングすると面倒だと思うよ
漏れはやる気が起きない（ｗ

950 ：名無しさん＠３周年：02/08/10 00:25 ID:2uHwbXlf

　げっ？　これって素数理論を解明したって事？　それとも推論？

951 ：名無しさん＠３周年：02/08/10 00:28 ID:RceDn5Cb

ふ～ん素数て無限にあるんだ。古いギネスブックに一番大きい素数ってのが
有った気がするんだが、俺の記憶違いか、間違いだったんだな、勉強になった。

952 ：名無しさん＠３周年：02/08/10 00:28 ID:PR5NiCMk

やはり宗教が分かっている国の国民って、
常に神様の事を感じているからひらめきとか
論理とか強いんだろうなぁ～。

対して、日本国民は２ちゃんねるやりすぎて
クールになりすぎたんだな、たぶん。

953 ：名無しさん＠３周年：02/08/10 00:29 ID:mlcTUBpc

>>942
http://pc3.2ch.net/tech/#3

954 ：名無しさん＠３周年：02/08/10 00:30 ID:+MBWiKKm

>>951
今わかってる中で最大の素数って意味だとおもう
πと同じようなかんじで

>>952
それは人間講座で藤原氏が言ってたねｗ

955 ：名無しさん＠３周年：02/08/10 00:30 ID:F8Gjukfy

>>943
歴史上、スッゴイのが前世紀にいたよ。
ラマヌジャンで検索して見れ。

956 ：953：02/08/10 00:31 ID:mlcTUBpc

ｽﾏｿしくった。逝きます。

957 ：名無しさん＠３周年：02/08/10 00:32 ID:PNC6Grpo

やべぇ。機密がばれちゃうぞ。
公開鍵暗号とかが素数つかってるんだったかな？

958 ：名無しさん＠３周年：02/08/10 00:32 ID:J2SZQy04

やっぱこういうネタレスがいっぱいあるのが２ｃｈの楽しいとこだよなぁ。政治関係になると
みんな知ったかぶりでマジ議論するからつまんない。

959 ：名無しさん＠３周年：02/08/10 00:32 ID:F8Gjukfy

>>950
リーマン予想の事？それならまだまだ。

960 ：名無しさん＠３周年：02/08/10 00:34 ID:SiYmw0dX

1000

961 ：名無しさん＠３周年：02/08/10 00:34 ID:F8Gjukfy

で、多項式時間で素数判定が解決できたら、具体的に何が出来るの？
詳しい方、プリーズ。

962 ：名無しさん＠３周年：02/08/10 00:35 ID:H12v4vWq

暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/

963 ： ◆gaChapSQ ：02/08/10 00:35 ID:tw58AxOY

>>961
阪神が優勝します

964 ：名無しさん＠３周年：02/08/10 00:36 ID:Oz11bLUy

さすが０を発明した国インド、とＤＱＮなネタレスをかましておいてっと。

でだ。ＵＮＩＸ板住人はこんどは素数判定対応の暗号をつくるのかvv

965 ：333：02/08/10 00:36 ID:WqoSIN+h

インド人がここまで優秀だとすると、象が世界を支えて、さらにでかい亀が象を載せてる概念は、実は正しいのではと思えてきた。
コペルニクスより、インド人のが理系は優秀な気がしないか？
おれはテレビや写真でしか丸い地球を見た事無いし。
テレビや写真なら、幽霊も見た事あるし。

966 ：名無しさん＠３周年：02/08/10 00:36 ID:2uHwbXlf

>>959

計算機の力で素数発生をカウントすると、予測より若干減ってくる奴ですね。

967 ：　：02/08/10 00:37 ID:gBUKWhBZ

>>961
現在使われてる暗号が破られやすくなって使い物にならなくなります。

968 ：333：02/08/10 00:37 ID:WqoSIN+h

初の1000チャレンジしてみマスタ。

969 ：名無しさん＠３周年：02/08/10 00:39 ID:QvgDIWKf

暗号だめぽっつーより
素数判定がＰで因数分解がＮＰなら、「合理的な時間で完全な暗号が作れることになりますた。」
というとてもおめでたい発表だと思うのだが

970 ：名無しさん＠３周年：02/08/10 00:39 ID:H12v4vWq

1001は素数ではない

971 ：名無しさん＠３周年：02/08/10 00:40 ID:F8Gjukfy

うーん、暗号は素数を使ってるんですか・・・
俺は思うに、楕円曲線の有理点とかで代用すれば、何の問題もないと
思うのですが、どうですか？

972 ：名無しさん＠３周年：02/08/10 00:40 ID:bsIGvpOM

>>961
お肌の年齢が10歳若返ります。

973 ：名無しさん＠３周年：02/08/10 00:40 ID:Kg6lNNDI

1000ですね

974 ：z：02/08/10 00:41 ID:m5NkR+BZ

７の倍数だな１００１は

975 ：名無しさん＠３周年：02/08/10 00:41 ID:mYxPVPdR

1の妄想スレタイのせいで>>957のような勘違いレスが次から次へと現れる。
1糾弾スレにならないのはクソスレにならないようにみんな気を使ってるから。
でも1は無邪気にスレ延びて喜んでる。まじむかつく。

…といいつつ数学ネタ提供した1にはちょこっと感謝。

976 ：名無しさん＠３周年：02/08/10 00:41 ID:H12v4vWq

1000を取るより最後の素数を取ったほうがいいように思う。
997か？

977 ：(；´Д｀)ﾊｧﾊｧ：02/08/10 00:41 ID:kFVvXkKi

>>970
1001=7×11×13

978 ：333：02/08/10 00:41 ID:WqoSIN+h

なんか、前の方と繰り返しになってきましたね。

でも素数判定がPでも、因数分解はNPでしょうか。
僕にはP=NPが証明されそうな予感がします。

979 ：名無しさん＠３周年：02/08/10 00:41 ID:+MBWiKKm

>>961
今までの方法だとある確率＜１でしか素数判定できなかったから
素数判定が失敗した場合はやり直してたんだけど
今回のアルゴリズムを使うと確率＝１で確実に素数判定できるようになるから
（たとえば、RSA）暗号での鍵生成の効率をあげることができるようになった。

980 ：333：02/08/10 00:42 ID:WqoSIN+h

>>976
さっそくこのアルゴリズムを使って、判定してくれ。

981 ：名無しさん＠３周年：02/08/10 00:43 ID:H12v4vWq

>>978
なんかインドの数学者がNP完全問題の多項式アルゴリズムを
書いて終了させてしまう予感

982 ：名無しさん＠３周年：02/08/10 00:43 ID:+0E4EHWy

そりゃーインドは
昔から
ハノイの塔を弄くって地球の滅亡を予期してんだから。
数千年にもおよぶ優秀な遺伝子同士の組合せがなせる技なのかなー。

983 ：名無しさん＠３周年：02/08/10 00:43 ID:4gDM8kMm

>>981
そして世界はインド人にびっくり。

984 ：名無しさん＠３周年：02/08/10 00:43 ID:06ktVnlm

俺がその素数だ！　　・・うそだけど。

985 ：　かべがみ。：02/08/10 00:44 ID:sIzJHm8H

ｗれｒ

986 ：名無しさん＠３周年：02/08/10 00:45 ID:+MBWiKKm

このスレPart2は必要ないよな

987 ：名無しさん＠３周年：02/08/10 00:45 ID:atn/8mco

素人

988 ：名無しさん＠３周年：02/08/10 00:45 ID:S9fu+ZIG

1000dayo

989 ：名無しさん＠３周年：02/08/10 00:45 ID:H12v4vWq

誘導

素数判定は「決定的」多項式時間で可能
http://science.2ch.net/test/read.cgi/math/1028813059/
暗号総崩れ-素数判定が多項式時間で可能
http://pc3.2ch.net/test/read.cgi/tech/1028877628/

990 ：942：02/08/10 00:45 ID:js5rPAIv

皆さん即レス感謝！！

2chていいなぁ。
ちょっとあっちに行ってきます。

991 ：名無しさん＠３周年：02/08/10 00:45 ID:S9fu+ZIG

1102.0531

992 ：名無しさん＠３周年：02/08/10 00:45 ID:cmK0Qdni

ノーベル賞？

993 ：名無しさん＠３周年：02/08/10 00:45 ID:S9fu+ZIG

45344

994 ：名無しさん＠３周年：02/08/10 00:45 ID:4gDM8kMm

おらおらおら

995 ：(　´ⅴ｀)ノ：02/08/10 00:45 ID:HM7Hiaou

>>929 感動したのれす。さんくす。

996 ：チコリータ?：02/08/10 00:45 ID:xQzSx/5Q

100000000000000000

997 ：チコリータ?：02/08/10 00:45 ID:xQzSx/5Q

1000000000000000000000

998 ：(；´Д｀)ﾊｧﾊｧ：02/08/10 00:46 ID:kFVvXkKi

　|　 | ∧
　|＿|Д｀)<1000get!!
　|文|⊂）
　|￣|∧|
￣￣￣￣￣

999 ：名無しさん＠３周年：02/08/10 00:46 ID:4gDM8kMm

ああああああああ

1000 ：名無しさん＠３周年：02/08/10 00:46 ID:atn/8mco

あほ

1001 ：１００１：Over 1000 Thread

このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。