ポラード・ロー素因数分解法
Pollard's rho algorithm
ポラード氏のロー法って感じの命名。ロー氏がいるわけではない。てかローは$ \rho のこと
仕組み
素因数を見つける部分
フロイドver
合成数$ n に対して、素因数の1つを$ p とする。
$ f(a) = a^2+c \pmod n として、$ x = f(x) と繰り返し適用することを考える。
$ p は$ n の約数なので、$ f は$ \Z / p\Z 上の関数とみなせて、$ x は$ \Z / p\Z 上どこかで循環する。
$ \mu 回でループするとき、$ x = f^i(a) 、$ y = f^{2i}(a) の差$ \left| x-y \right| は$ 2i - i \equiv 0 \pmod \mu のとき$ p の倍数となる。
よって、$ \gcd( \left| x-y \right|, n) \gt 1 なる$ x, y が見つかるまで$ f を回せばいい。
ブレントver
$ x = f^{2^r}(a) 、$ y = f^{2^r+k}(a) とすることで、$ f の計算回数を削減できる。
流れ
$ n の素因数$ p を見つける → $ n を$ p で割れるだけ割る → 繰り返して$ n が素数か$ 1 になったら終了
計算量
$ f を回す回数が$ 1.177 \sqrt p 回で、$ \left| x-y \right| \equiv 0 \pmod p となる確率が$ 1/2 になるらしい。
$ p \le \sqrt n だから、約数を1つ見つけるのに$ O(n^{1/4}) 回。$ \gcd に$ O(\log n) かかるので、全体で$ O(n^{1/4}\log n) かかる。
参考