よしいずの雑記帳

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