はじめに
Pollardのρ法は素因数分解や離散対数問題を高速に計算する乱択アルゴリズムとして知られています。本稿ではPollardのρ法の動作原理を解説し、とくにPRNGに対する十分条件を与えます。
本稿ではp \le qを素数とし、半素数N = p qの素因数分解を考えます。また、実装上のテクニックは他に譲ります。
Pollardの\rho法
誕生日のパラドクス
誕生日のパラドクスは「無作為に人を23人以上集めると、50\%の確率で誕生日が被る」という事実が直感に反することを言います。これを一般化すると、「N以下の自然数から無作為に\Theta(\sqrt{N})個選ぶと、50\%程度の確率で重複する」という定理が得られます。
簡単な証明
k < N個の相異なる数が生成される確率は、スターリングの公式より、次のように近似されます。
p_k = \prod_{0 \le i < k} \frac{N-i}{N} = \frac{1}{N^k}\frac{N!}{(N-k)!} \sim \frac{1}{e^k} \left(\frac{N}{N-k}\right)^{N-k+\frac{1}{2}}
ここで、k \ll Nを仮定します。
\log p_k = -k - \left(N - k - \frac{1}{2} \right) \log \left(1 + \frac{k}{N}\right) \sim -k + \left(N - k - \frac{1}{2} \right)\frac{k}{N}
したがって、p_k \ge 1/2をみたす最小のkは次式で近似されます。
2 k^2 - k + 2 N \log 2 = 0 \space \therefore k = \frac{1 + \sqrt{1 + 16 N \log 2}}{4} = \Theta(\sqrt{N})
Nが十分大きいときに、k \ll Nが成り立ちます。
N以下の乱数を\Theta(\sqrt{p})個生成することを考えます。また、i番目の乱数をr_iとかきます。pがNの約数であることに注意すると、誕生日のパラドクスより、r_i \equiv r_j \pmod p \, (i \neq j)を満足するペアが約50\%の確率で得られることが分かります。r_i \not \equiv r_j \pmod Nのとき、\gcd(r_i - r_j, N) = pより素因数を発見できます。
\Theta(\sqrt{p})個の乱数からr_i \equiv r_j \pmod pを満足するペアを愚直に探すと、計算量はO(p)です。これでは、試し割法からあまり改善していません。あるいは、[0, N)からランダムに選んだ数とNのGCDを調べるよりも定数倍悪化しているという見方もできます。つまり、真の乱数を使うのは良い方法ではありません。
疑似乱数生成器
直前の乱数から次の乱数が生成できる特別な疑似乱数生成器（pseudorandom number generator, PRNG）を考えます。これをfとおくと、r_{i+1} = f(r_i)とかけます。乱数がN種類しかないので、オートマトンにただ1つのループが出現します。これが\rho法という名前の由来です。
PRNGに次の制約を追加します。Nの任意の約数でもなり立つことに注意しましょう。
x \equiv y \pmod N \Rightarrow f(x) \equiv f(y) \pmod N
x, yがともにループ上にあるとき、任意の自然数kについてf^k(x) \equiv f^k(y) \pmod Nが成り立ちます。ループ上で間隔を保ったままシフトしてもよいので、xとyの距離だけが問題になります。ループ上の点を1つ求めることができれば、O(\sqrt{p})で素因数分解できます。
ループ上に良いペアがない場合は、別のPRNGを試す必要があります。以上より、Pollardの\rho法で求められるPRNGの十分条件が得られました。
- 直前の乱数のみから次の乱数が決まること
-
x \equiv y \pmod N \Rightarrow f(x) \equiv f(y) \pmod Nが成り立つこと
- ループの周期が長いこと
- 乱数としての統計的性質がよいこと
まとめ
Pollardの\rho法の動作原理を解説しました。とくに、PRNGに求められる十分条件について述べました。多くの解説記事ではPRNGとしてf(x) = x^2 + c \pmod Nが採用されていますが、これは条件を満たしています。一般に、多項式であれば十分です。
線形合同法も条件を満たすことは注目に値します。なぜなら、線形合同法は対数時間でジャンプできるので、適当な初期値からNステップジャンプすることで、ループ上の点が得られるからです。これはパフォーマンスの改善につながります。残念ながら、筆者の手元で試した限りでは二次合同法の方がパフォーマンスに優れていたので、線形合同法はあまり良い選択ではないようです。
Discussion