ポラード・ロー素因数分解法
1980年、リチャード・ブレントはこのアルゴリズムを変形して高速化したものを発表した。彼はポラードと同じ考え方を基本としたが、フロイドの循環検出法よりも高速に循環を検出する方法を使った。そのアルゴリズムは以下の通りである。
入力: n、素因数分解対象の整数; x0、ここで 0 ≤ x0 ≤ n; m、ここで m > 0; f(x)、n を法とする擬似乱数発生関数
出力: nの自明でない約数、または失敗
y ← x0, r ← 1, q ← 1.
Do: x ← y For i = 1 To r: y ← f(y) k ← 0 Do: ys ← y For i = 1 To min(m, r − k): y ← f(y) q ← (q × |x − y|) mod n g ← GCD(q, n) k ← k + m Until (k ≥ r or g > 1) r ← 2r
Until g > 1
If g = n then Do: ys ← f(ys) g ← GCD(|x − ys|, n) Until g > 1
If g = n then return failure, else return g