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): とほほ。論文のrepeat〜untilのかかる範囲を勘違いしたうえなんかいろいろ間違ってた… 直したら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