ポラード・ロー素因数分解法
入力: n、素因数分解すべき整数; f(x)、n を法とする擬似乱数発生関数
出力: nの自明でない約数、または失敗
x ← 2, y ← 2; d ← 1
While d = 1: x ← f(x) y ← f(f(y)) d ← GCD(|x − y|, n)
If d = n, return failure.
Else, return d.
このアルゴリズムは n が素数の場合常に失敗するが、合成数であっても失敗する場合がある。後者の場合、f(x) を変えて再試行する。f(x) としては例えば線形合同法などが考えられる。また、上記アルゴリズムでは1つの約数しか見つけられないので、完全な素因数分解を行うには、これを繰り返し適用する必要がある。また、実装に際しては、対象とする数が通常の整数型では表せない桁数であることを考慮する必要がある。