ポラード・ロー素因数分解法

ポラード・ロー素因数分解法（英: Pollard's rho algorithm）は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラード（英語: John Pollard）が発明した。合成数を素因数に効率的に分解する。

概念

一般に素因数分解は、対象の数 n について、その平方根以下の全ての素数について n を割ってみる。しかし、これは n が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。

このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 x と y が p で割り切れるには、ランダムに $1.177{\sqrt {p}}$ 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている（誕生日のパラドックスを参照）。p が素因数分解したい n の素因数であるとき、p で $\left|x-y\right|$ も n も割り切れるので、 $1<\gcd \left(|x-y|,n\right)\leq n$ が成り立つ。

従ってこのアルゴリズムは、擬似乱数発生に n を法として使う。同じ乱数列を2回利用する。つまり、繰り返し毎に一方は順次擬似乱数列を生成し、もう一方は1つ飛びに擬似乱数列を利用する。前者を x、後者を y とする。繰り返し毎に |x − y| と n の最大公約数(GCD)を求める。このGCDが n になった場合、このアルゴリズムは失敗して停止する。というのは、これは x = y であることを意味し、フロイドの循環検出法により、それ以降の擬似乱数列がそれまでの繰り返しになってしまうことを示しているからである。

アルゴリズム

入力: n、素因数分解すべき整数; f(x)、n を法とする擬似乱数発生関数

出力: nの自明でない約数、または失敗

x ← 2, y ← 2; d ← 1
While d = 1:
1. x ← f(x)
2. y ← f(f(y))
3. d ← GCD(|x − y|, n)
If d = n, return failure.
Else, return d.

このアルゴリズムは n が素数の場合常に失敗するが、合成数であっても失敗する場合がある。後者の場合、f(x) を変えて再試行する。f(x) としては例えば線形合同法などが考えられる。また、上記アルゴリズムでは1つの約数しか見つけられないので、完全な素因数分解を行うには、これを繰り返し適用する必要がある。また、実装に際しては、対象とする数が通常の整数型では表せない桁数であることを考慮する必要がある。

リチャード・ブレントによる変形

1980年、リチャード・ブレントはこのアルゴリズムを変形して高速化したものを発表した。彼はポラードと同じ考え方を基本としたが、フロイドの循環検出法よりも高速に循環を検出する方法を使った。そのアルゴリズムは以下の通りである。

入力: n、素因数分解対象の整数; x₀、ここで 0 ≤ x₀ ≤ n; m、ここで m > 0; f(x)、n を法とする擬似乱数発生関数

出力: nの自明でない約数、または失敗

y ← x₀, r ← 1, q ← 1.
Do:
1. x ← y
2. For i = 1 To r:
  1. y ← f(y)
3. k ← 0
4. Do:
  1. ys ← y
  2. For i = 1 To min(m, r − k):
    1. y ← f(y)
    2. q ← (q × |x − y|) mod n
  3. g ← GCD(q, n)
  4. k ← k + m
5. Until (k ≥ r or g > 1)
6. r ← 2r
Until g > 1
If g = n then
1. Do:
  1. ys ← f(ys)
  2. g ← GCD(|x − ys|, n)
2. Until g > 1
If g = n then return failure, else return g

使用例

このアルゴリズムは小さな素因数のある数については非常に高速である。例えば、733MHz のワークステーションで全く最適化していないこのアルゴリズムを実装すると、0.5秒以内に6番目のフェルマー数 18446744073709551617（20桁の数値）の素因数 274177 を発見できる。しかし、2つの10桁の素数の積で与えられるほぼ同じ大きさの半素数 10023859281455311421 については、同じワークステーションで9秒ほどかかった。なお、f としては以下のような多項式を用いた:

f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.

このアルゴリズムでの成功例としては、ポラードとブレントによる8番目のフェルマー数の素因数分解がある。彼らはブレントの変形アルゴリズムを使ってそれまで知られていなかった素因数を発見した。F₈ の完全な素因数分解は、UNIVAC 1100/42 で2時間かかった。

素因数分解の具体例

n = 8051 で、f(x) = x² + 1 mod 8051 とする。

i	x_i	y_i	GCD(\|x_i − y_i\|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

擬似乱数発生関数の定数部分を変更すると、もう一方の素因数 83 が求められる。

計算量

このアルゴリズムでは、実行時間と素因数発見確率がトレードオフの関係にある。n が同じ桁数の2種類の素数の積であるとき、O(n^1/4 polylog(n)) ステップ実行することで発見確率が約50%となる。なお、これはヒューリスティックによる概算であり、このアルゴリズムの正確な解析は未解決の問題である。

出典

[脚注の使い方]

参考文献

Brent, Richard P. (1980-06-01). “An Improved Monte Carlo Factorization Algorithm”. BIT (BIT Computer Science and Numerical Mathematics) 20 (2): 176-184. doi:10.1007/BF01933190.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). “Section 31.9: Integer factorization”. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 896–901. ISBN 0-262-03293-7 (this section discusses only Pollard's rho algorithm).