大きな数の因数を発見的に求めるρ法(Pollardのρヒューリスティック)をRubyで実装しました。 # 2個の素数の積を因数分解する def factor_two(given) start = Time.now one = rho(given) another = given / one elapsed = Time.now - start puts "#{given} = #{one} * #{another} (#{elapsed} sec)" end # 『アルゴリズムイントロダクション』第3巻p.196 # 「Pollardのρヒューリスティック」で因数を探す def rho(n) i = 1 x = rand(n) y = x k = 2 loop do i += 1 x = (x * x - 1) % n f = n.gcd(y - x) if f != 1 and f !=
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く