Pollard p-1 因子分解法

一种素因数分解算法，可以以单步或双步形式实现。在单步版本中，如果 是小素数的乘积，则可以通过找到一个 来找到数字 的素因子 ，使得

其中 ，其中 是一个大数，且 。那么，由于 ，，因此 。因此，很有可能 ，在这种情况下， (其中 GCD 是最大公约数) 将是 的一个非平凡因子。

在双步版本中，如果 是小素数和一个较大的素数的乘积，则可以找到素因子 。