Path: news.ccsf.jp!4bn.ne.jp!not-for-mail
From: Yoshitaka Ikeda <ikeda@4bn.ne.jp>
Newsgroups: japan.chat
Subject: Re: =?iso-2022-jp?B?GyRCQUcweD90SiwychsoQg==?=
Date: Mon, 30 Mar 2009 12:56:55 +0900
Organization: Yonbetsu Netzwerk
Lines: 40
Message-ID: <86zlf38xyw.fsf@bsd2.4bn.ne.jp>
References: <gqdfar$8gv$1@film.rlss.okayama-u.ac.jp> <868wms3atn.fsf@bsd2.4bn.ne.jp> <20090326212612.e0aabd26.tuc@vfemail.net> <864oxfrxqy.fsf@bsd2.4bn.ne.jp> <20090328233533.9f0e6ffa.tuc@vfemail.net>
NNTP-Posting-Host: bsd2.4bn.ne.jp
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-2022-jp
X-Trace: bsd2.4bn.ne.jp 1238385415 29464 133.31.107.233 (30 Mar 2009 03:56:55 GMT)
X-Complaints-To: ikeda@4bn.ne.jp
NNTP-Posting-Date: Mon, 30 Mar 2009 03:56:55 +0000 (UTC)
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.1 (berkeley-unix)
Cancel-Lock: sha1:kPYzcQRAnlzAr4eoFeQ1uIxKGwI=
Xref: news.ccsf.jp japan.chat:36063

Taku <tuc@vfemail.net> writes:

> On Fri, 27 Mar 2009 20:49:57 +0900
> Yoshitaka Ikeda <ikeda@4bn.ne.jp> wrote:
>
>> もし、500桁の素因数分解ができるようなプログラムを作れるのなら、
>> なんらかのお誘いはどこかの国から来ると思いますよ。そういうレベルの話。
>> 
>> ちょっとふるいけど、
>> http://itpro.nikkeibp.co.jp/article/NEWS/20070521/271718/
>> 1017bit=300桁の素因数分解が世界記録ですから。
>> 
>> すくなくとも、それを学会発表したら論文賞の一つも確実にもらえるレベルです。
>
> プログラムが難しいのでしょうか。
> それとも，効率良く計算するためのプログラム？
> 計算機の力がないので，プログラムが難しくなるのでしょうか。

三つとも該当すると思ってください。
今時だと数体ふるい法という方法をとることになります。
アルゴリズムを理解すること自体が難しいです。それの実装もかなり大変。

効率よく計算するためのプログラムも難しいですが、そもそもちゃんと
動く物を作るのが難しいというレベルです。ついでに書いておくと、
どれくらいのメモリ領域が許されるか、並列演算をするのならその並列演算で
どれくらいのデータのやりとりが行われるのかをちゃんと見極めて組まないと
どこにボトルネックがあるかわかりません。

世界最高レベルのプログラムで並列演算を行っても300桁の素因数分解には、
年のレベルの計算時間がかかります。200桁=660bit程サイズがでかいわけで、
単純に計算はできないけど、数兆年レベルでは解けないことは容易にわかります。
正直桁が違いすぎます。

アルゴリズムを修正することによってしか素因数分解は望めないと思います。
計算機の多少の発展では全く歯が立たないレベルの話です。

-- 
I LOVE SNOOPY!  でつ
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp
My Honeypot: honey@4bn.ne.jp  <-don't send this address