Pollard Rho Algorithm
Pollardのrho法は、擬似乱数列x_{i+1}=f(x_i) mod nを使って大きな数の因数を見つける手法であり、期待計算量はO(n^(1/4))である。
目的
中規模の整数を素因数分解する。弱いRSAモジュラスへの攻撃に使われる。
メカニズム
f(x)=x^2+c mod nで数列を生成し、Floydのアルゴリズムでサイクルを検出する。サイクル上でgcd(|x_i-x_j|, n)が非自明な因数を与えることがある。誕生日のパラドックスにより、期待ステップ数はO(p^(1/2))（pは最小素因数）である。
ユースケース
- 整数の素因数分解（ファクタリング）
- RSAへの攻撃
- 数論的アルゴリズム