Path: news.ccsf.jp!4bn.ne.jp!not-for-mail From: Yoshitaka Ikeda Newsgroups: japan.chat Subject: Re: =?iso-2022-jp?B?GyRCQUcweD90SiwychsoQg==?= Date: Thu, 26 Mar 2009 18:14:28 +0900 Organization: Yonbetsu Netzwerk Lines: 26 Message-ID: <868wms3atn.fsf@bsd2.4bn.ne.jp> References: 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 1238058869 37385 133.31.107.233 (26 Mar 2009 09:14:29 GMT) X-Complaints-To: ikeda@4bn.ne.jp NNTP-Posting-Date: Thu, 26 Mar 2009 09:14:29 +0000 (UTC) User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.1 (berkeley-unix) Cancel-Lock: sha1:ItP/lDj9gS3s55smbP4jy3O+2Jg= Xref: news.ccsf.jp japan.chat:36040 "Hiromu Hasegawa" writes: > 素因数分解何年か前実質１４桁作った、14桁計算させてみれば一瞬で計算する。 > あんなもん人間のする仕事でない。 > そこで５００桁計算するプログラム作ってみたい、教授の玩具には成るだろう。 どんなアルゴリズムで作ったんでしょうか。 今時のパソコンであれば、14桁の素因数分解であれば試行割り算法で充分可能 だと思います。たぶん、19桁くらいまでは余裕。(64bit変数使えば19桁くらい 表現可能) 500桁は1600bitくらいあるので、ちょっと現状では無理だと思います。 素人が使うコンピュータのレベルだと100bitくらい(30桁程度)が挑戦にいい感じの サイズだと思います。 このレベルだと試行割り算法はたぶん無理です。素人目にわかりやすいのは 2次ふるい法だと思います。2次ふるい法なら100bitくらいなら計算できるはず です。 多倍長演算が必要になります。多倍長演算実装するのは難しいかもしれません。 その場合は、gnuMPあたりのライブラリを使うとよいかもしれません。 -- I LOVE SNOOPY! でつ Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp My Honeypot: honey@4bn.ne.jp <-don't send this address