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