ポラード・ロー素因数分解法
このアルゴリズムは小さな素因数のある数については非常に高速である。例えば、733MHz のワークステーションで全く最適化していないこのアルゴリズムを実装すると、0.5秒以内に6番目のフェルマー数 18446744073709551617(20桁の数値)の素因数 274177 を発見できる。しかし、2つの10桁の素数の積で与えられるほぼ同じ大きさの半素数 10023859281455311421 については、同じワークステーションで9秒ほどかかった。なお、f としては以下のような多項式を用いた:
f ( x ) = x 2 + c mod n , c ≠ 0 , − 2. {\displaystyle f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.}
このアルゴリズムでの成功例としては、ポラードとブレントによる8番目のフェルマー数の素因数分解がある。彼らはブレントの変形アルゴリズムを使ってそれまで知られていなかった素因数を発見した。F8 の完全な素因数分解は、UNIVAC 1100/42 で2時間かかった。
n = 8051 で、f(x) = x + 1 mod 8051 とする。
擬似乱数発生関数の定数部分を変更すると、もう一方の素因数 83 が求められる。
ポラード・ロー素因数分解法(英: Pollard's rho algorithm)は、特殊用途の素因数分解アルゴリズム。1975年、ジョン・ポラード(英語: John Pollard)が発明した。合成数を素因数に効率的に分解する。
一般に素因数分解は、対象の数 n について、その平方根以下の全ての素数について n を割ってみる。しかし、これは n が大きい場合に対象となる全ての素数が明らかでないという問題が生じる。ポラード・ロー素因数分解法は、そのような場合に大きな素因数を確率的に探す乱択アルゴリズムである。
このアルゴリズムはフロイドの循環検出法に基づいており、また2つの数 x と y が p で割り切れるには、ランダムに 1.177 p {\displaystyle 1.177{\sqrt {p}}} 個の数を選んだとき半分以上の確率で共に割り切れるという観測結果に基づいている(誕生日のパラドックスを参照)。p が素因数分解したい n の素因数であるとき、p で | x − y | {\displaystyle \left|x-y\right|} も n も割り切れるので、 1 < gcd ( | x − y | , n ) ≤ n {\displaystyle 1<\gcd \left(|x-y|,n\right)\leq n} が成り立つ。
従ってこのアルゴリズムは、擬似乱数発生に n を法として使う。同じ乱数列を2回利用する。つまり、繰り返し毎に一方は順次擬似乱数列を生成し、もう一方は1つ飛びに擬似乱数列を利用する。前者を x、後者を y とする。繰り返し毎に |x − y| と n の最大公約数(GCD)を求める。このGCDが n になった場合、このアルゴリズムは失敗して停止する。というのは、これは x = y であることを意味し、フロイドの循環検出法により、それ以降の擬似乱数列がそれまでの繰り返しになってしまうことを示しているからである。