Island Life

< 楽器 | 時代はめぐる〜 >

2013/02/16

素因数分解

404 Blog Not Found : Math - おまいら素因数分解どうしてますか?

しかし、因数分解すべき数字が78桁だったりしたらどうでしょう?

このくらい大きくなるとGeneral Number Field Sieveの出番だけど、まだGaucheのmath.primeには実装してないので 敢えて実装済みのMonte Carlo Factorizationで挑戦してみよう。

gosh> (use math.prime)
#<undef>
gosh> (time (mc-factorize 280671392065546467397265294532969672241810318954163887187279320454220348884327))
;(time (mc-factorize 280671392065546467397265294532969672241810318954163 ...
; real 552.461
; user 552.310
; sys    0.110
(162425297 215940091 358456949 369941863 369941863 479871607 706170617 481362815814826159)

9分ちょいかかった。 なおのMonte Carlo Factorizationの推奨入力範囲は10進数でせいぜい20桁程度、とのことだ。

しかし引用元blogにあるみたいにGNFSでこれが1秒で計算できるなら、 Monte Carlo FactorizationをスキップしてGNFS実装した方が良かったかなあ。 尤もGaucheはbignumの乗除算が遅いから、実用を考えるなら最初から外部ライブラリを使うべきで、Schemeで実装するのは単なる自己満足にすぎないんだけど。

★ ★ ★

(追記2013/02/19 07:09:20 UTC): 素因数分解プログラムについてのメモ - 再帰の反復 を見ると、どうも私のmc-factorizeの実装がタコっぽいな。後で調べる。

(追記2013/02/19 13:43:40 UTC): とほほ。論文のrepeatuntilのかかる範囲を勘違いしたうえなんかいろいろ間違ってた… 直したら1秒以下でいけた。Brentさんごめんなさい。

gosh> (time (mc-factorize 280671392065546467397265294532969672241810318954163887187279320454220348884327))
;(time (mc-factorize 280671392065546467397265294532969672241810318954163 ...
; real   0.716
; user   0.710
; sys    0.000
(162425297 215940091 358456949 369941863 369941863 479871607 706170617 481362815814826159)

Tags: Programming, Gauche

Past comment(s)

m.ukai (2013/02/18 11:39:55):

いくらなんでも GNFS で瞬殺は無理です。 1時間とかのオーダーではかかるはずで、 それに80桁前後ならまだ MPQS系のほうが速いはずです。

小飼さんとこの各種結果は、ECM系による効果だと思います。 msieve でも -e 積んでますし。 (素因数の桁数が小さいので B1=100 くらいで何回か回せば全部見つかる)

shiro (2013/02/18 12:38:56):

なんと、そうですかあ。じゃあLenstraも実装しないとだめかなあ。確かにこの問題に関しては素因数が9桁のオーダーなんでわりと速く見つけられるんですね。

Post a comment

Name: