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
