Pollard p-1 因子分解法

一種素因數分解演算法，可以以單步或雙步形式實現。在單步版本中，如果 是小素數的乘積，則可以透過找到一個 來找到數字 的素因子 ，使得

其中 ，其中 是一個大數，且 。那麼，由於 ，，因此 。因此，很有可能 ，在這種情況下， (其中 GCD 是最大公約數) 將是 的一個非平凡因子。

在雙步版本中，如果 是小素數和一個較大的素數的乘積，則可以找到素因子 。