Pollard rho 因子分解法

一種 素因數分解演算法，也稱為 Pollard 蒙特卡洛因子分解法。Pollard 因子分解法有兩個方面。第一個方面是迭代公式直到它陷入迴圈的想法。設 , 其中 是要分解的數， 和 是其未知的素因子。迭代公式

(1)

或幾乎任何多項式公式（ 是一個例外）對於任何初始值 都會產生一個最終陷入迴圈的數字序列。 s 變為迴圈的預期時間和迴圈的預期長度都與 成正比。

然而，由於 其中 和 互質，中國剩餘定理保證了 (mod ) 的每個值唯一對應於值對 (), )。此外，序列 s 遵循完全相同的公式模 和 ，即

			(2)
			(3)

因此，序列 (mod ) 將陷入長度約為 的短得多的迴圈。可以直接驗證兩個值 和 具有相同的值 (mod )，透過計算

(4)

這等於 。

Pollard 方法的第二部分涉及檢測序列已變為週期性的事實。Pollard 的建議是使用歸因於 Floyd 的想法，即比較 和 對於所有 。Brent 因子分解法中使用了不同的方法。

在最壞的情況下，Pollard 演算法可能非常慢。