Pollardのロー法による因数分解プログラムの例

Rubyによる、Pollardのロー法を用いた因数分解プログラムの例。

Pollardのロー法とは

与えられた自然数の因数を求めるアルゴリズムのうち、乱数を用いた発見的な方法はモンテカルロ法と呼ばれる。Pollard(ポラード)のロー法は、モンテカルロ法の一種である。

Pollardのロー法は、有限集合 S から S 自身への乱数関数 f によって定まる乱数列 s, f(s), f(f(s)), ... を利用する。ただし、最初の s は S の中からランダムに一つ選ぶ。この数列は、どこかで同じ値が現れ(∵部屋割り論法)、その後は同じ数の並びが周期的に繰り返される。その様子がギリシャ文字のρ(ロー)に似ていることから、ロー法と名づけられた(らしい)。

アイデアを大雑把に説明すれば、n を自然数、p を n の最小の素因数とし、f(x) = x^2 + 1 mod p、F(x) = x^2 + 1 mod n とするとき、gcd(F^{i}(s)-F^{2i}(s), n) (i=1, 2, ...) を計算すると、その中で n の自明でない約数となるものが、運がよければ O(√p) の回数のステップで見つかる、というものである。

活用例として、Fermat数 F_8=2^(2^8)+1 が、Pollardのロー法の変形を使って因数分解された(BrentとPollardによる。1981年)。

Rubyによるプログラム

『素数全書』のアルゴリズム5.2.1をもとに、プログラムをRubyで記述。

#! ruby -Ks

def gcd(a, b)
  a = -a if a < 0
  b = -b if b < 0
  while b > 0
    a, b = b, a % b
  end
  a
end

def f(x, a, n)
  (x * x + a) % n
end

def pollard_rho(n)
  x = y = rand(n)     # 0≦x, y≦n-1
  a = 1 + rand(n-3)   # 1≦a≦n-3
  begin
    x = f(x, a, n)
    y = f(y, a, n)
    y = f(y, a, n)    # f() を2回適用する
    d = gcd(x-y, n)
  end until d > 1
  d
end

def factor(n)
  d = pollard_rho(n)
  print "#{d}"
  while n > d
    n /= d
    d = pollard_rho(n)
    print " * #{d}"
  end
end

# ======================================

if $0 == __FILE__ 

factor(121439531096594251777) #=> 30894471809 * 3930785153

end

注意事項

  • 上のプログラムで得られる各因数 d は必ずしも素数とは限らない。
  • もとの数が出力されたからといって、それが素数とは限らない。
  • 求まる因数は必ずしも小さい順とは限らない。
  • a の範囲が 1≦a≦n-3 なのは、a=0, -2 の場合に関数が「十分に乱雑」にならないことが知られているから。

参考文献

  • Crandall, R., Pomerance, C.(著), 和田秀男(監訳): 素数全書 計算からのアプローチ, 朝倉書店, 2010

【theme : 数学
【genre : 学問・文化・芸術

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示