なんで素因数分解って難しいと言われてるの？

1 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:46:27.28 ID:JpRdJ3wg0.net

小さい素数から割れるか確かめてけばいいだけじゃん

2 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:46:50.69 ID:J0nhWcJ60.net

カズミちゃん！

3 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:47:12.32 ID:0yZzt0Mg0.net

誰がいってんの？脳内？

4 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:47:18.65 ID:WTd+v0Ee0.net

何やったっけ
簡単な例題出して

5 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:48:02.83 ID:JpRdJ3wg0.net

>>3
素因数分解ってなんか暗号とかPWに使われてんじゃないの？

6 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:48:29.16 ID:i0++9Y1+0.net

143678893

7 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:49:09.95 ID:GaBSVPAc0.net

いわれてないです。

8 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:49:34.36 ID:dRL6nkQI0.net

では500桁の数を因数分解してください

9 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:49:38.86 ID:qK/+WI3/0.net

>>5
数百桁の素数とかに行きつくまでどれだけの時間かかるかわかってんの

10 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:49:48.50 ID:V4gnItnv0.net

8621906を素因数分解して

11 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:50:02.17 ID:+L9EAr9E0.net

数十桁とかは無理

12 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:50:30.71 ID:JpRdJ3wg0.net

>>6
コンピュータならこれより小さい素数から順に割れるか確かめていけば瞬殺じゃないの？

13 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:50:33.46 ID:GaBSVPAc0.net

100

14 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:51:21.66 ID:I/h7Nz2bi.net

数2勉強しろ

15 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:51:41.93 ID:JpRdJ3wg0.net

>>9
コンピュータでも？

16 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:54:14.07 ID:xNOiEfTr0.net

Aが二つの大きな素数p, qを用意し、Bに積 pq の値を教える
Bは与えられた積 pq から二つの素数 p, qを現実的な時間で割り出せるか

17 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:54:41.72 ID:dRL6nkQI0.net

>>15
「100桁の整数」って具体的にはこんなのだぞ
いくら高速なコンピュータでも時間かかりまくるわ

724873291484256327239859265786325262346523875632857239576540680720303462324151857475752344

18 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:54:52.35 ID:H4UcMUIA0.net

10^100ミリ秒はおよそ3×10^89年

19 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:55:45.62 ID:V4gnItnv0.net

>>17
スパコンのスペックよく調べてみろ

20 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 01:59:52.23 ID:JpRdJ3wg0.net

>>16
Bって現代の科学全て利用できてもそんな不利なの？

21 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:00:42.03 ID:TclBVzKT0.net

ポイントは
2秒で問題作れるのに解くには数何百倍もの時間がかかるってところ
問題を作るには適当な素数２つ用意すればいい
例えば13×17で221

問題を解くには1からひとつずつ試していくしか(今のところ)方法はない

この問題を作る労力と問題を解く労力の違いがぽいんとなのよ

22 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:01:54.09 ID:JpRdJ3wg0.net

>>21
でも実際の計算は割り算でしょ
スパコンなら余裕そうなんだけど

23 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:03:28.52 ID:TclBVzKT0.net

>>20
不利やで
世界中の科学を動員しても現実的に解けないから
世界中の暗号通信に利用されてるんやで

24 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:04:22.15 ID:OMfzS+Od0.net

なんでRSA暗号が使われてるか考えてみろよ
お前がここでなんて言おうが多項式時間で解く方法は未だ見つかってないんだよ

25 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:04:50.99 ID:dRL6nkQI0.net

>>22
50桁以下の素数の数だけで10^48個くらいある
対して10PFLOPSのスパコンは1秒に10^16回しか演算できない
1年フル稼働させても10^24回程度

26 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:05:32.07 ID:NN3MDQMe0.net

RSA暗号も知らない馬鹿が何でこんな多いの

27 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:05:59.72 ID:TclBVzKT0.net

>>22
スパコンならある程度の桁までなら大丈夫だよ
ただし、問題を作る側は超簡単に難易度をあげることができる
桁をひとつ、つまり数字をひとつ増やすだけで
素因数分解にかかる手間は何倍にもなる
スパコンが解けない桁まで増やせばいいだけ

28 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:06:12.72 ID:JpRdJ3wg0.net

>>25
わかった
無理なんだね
数学って不思議だな

29 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:06:21.42 ID:gNFkvOw70.net

量子コンピューターが実現したら一瞬で解けるらしいな

30 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:07:25.63 ID:xNOiEfTr0.net

>>20
インターネットで個人情報のやりとりをするときにはRSA暗号っていう技術が使われてる
何を根拠に安全だと言ってるか調べてみ？

31 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:08:01.85 ID:JpRdJ3wg0.net

>>27
でかい素数見つけるのは簡単？

32 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:08:29.02 ID:TclBVzKT0.net

その場合は量子コンピューターで暗号作ればいいんだけどね

33 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:08:46.56 ID:xNOiEfTr0.net

じゃあここで面白いことしてみる？

34 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:09:32.70 ID:C8z+LdMU0.net

CAB方式ってどう？

35 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:10:02.41 ID:TclBVzKT0.net

>>31
難しいに決まってるだろ
素数の見付け方が素因数分解できるか1からためしていくしかないんだから

36 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:10:32.66 ID:JpRdJ3wg0.net

>>35
じゃあAも問題つくるのむずくね？

37 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:13:55.15 ID:TclBVzKT0.net

>>36
解くほうが何倍も難しいっていうのがポイントなの

38 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:14:54.89 ID:xNOiEfTr0.net

素数から離れちゃうしやっぱいいや

39 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:15:00.49 ID:JpRdJ3wg0.net

>>37
何倍くらいむずいん？

40 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:15:39.31 ID:0F8FnPtd0.net

>>34
アルゴリズムが公開されてないからなんともいえん
会社作って儲ける気満々だから広く使われないと思う

41 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:15:47.29 ID:d2SrSaIQ0.net

遂に解読不能究極暗号「CAB方式」特許内容が公開
http://wc2014.2ch.net/test/read.cgi/math/1409658191/
解説よろしく

42 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:15:50.31 ID:JpRdJ3wg0.net

>>38
やってくれ 興味深い

43 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:17:33.89 ID:sxwWbo8x0.net

あ、それなら昨日俺が暗算で解いたよ

44 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:18:21.35 ID:JpRdJ3wg0.net

>>41
すげえな
でももし絶対解けないってのもなんかツマラナイなw

45 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:18:21.79 ID:02xjyRXu0.net

数学の先生がでっかい素数見つけると高く売れるって言ってたけどまじ？

46 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:21:51.27 ID:TclBVzKT0.net

>>39
桁が増えると加速度的に難しくなっていくぞ
人間が感覚でわかる範囲を越えるとお手上げ

47 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:21:51.88 ID:K/lNE2jHI.net

>>41
これ>>24が言ってるみたいに解けない証明ができたならP≠NPの証明にもなってるの？

48 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:24:44.97 ID:xNOiEfTr0.net

これ読んでおけ
http://d.hatena.ne.jp/tondol/touch/20070608/1181301219

49 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:25:05.90 ID:JpRdJ3wg0.net

>>47
なにそれ詳しく

50 ：以下、＼(^o^)／でVIPがお送りします：2014/09/07(日) 02:25:56.43 ID:JpRdJ3wg0.net

>>48
俺の疑問ドンピシャに答えてくれてる