algorithm - Pollard Rho 分解方法实现

Question

每次我使用 Pollard Rho 分解方法分解一个数字时，是否有必要在 Pollard Rho 分解之前检查它的素数？如果是，那么每次我想分解任何数字时，我都必须实施米勒拉宾的素性检验或任何素性检验，而且我必须处理强伪素数，这不是很复杂吗？有没有简单且更快的方法来处理这个问题？（我对最多 10 位的数字使用这些测试）

Answer 1

是的，在申请 Pollard Rho 之前，您必须检查您所分解的数字是复合的。如果它是素数，gcd 步骤将始终返回 1，因为素数始终与其他数字互质，并且 Pollard Rho 将永远运行而没有结果。

对于最多十位数的数字，不需要 Pollard Rho。简单的试除法就足够快了，因为你只需要小于 100000 的素数，而且只有 9592 个。