Pollard Rho分解方法的实现

Question

每次我使用Pollard Rho分解方法分解一个数时，有必要在Pollard Rho分解之前检查它的素性吗？如果是，那么我必须实现Miller Rabin的素性测试或任何素性测试，每次我想要分解任何数字时，我仍然必须处理强伪素数，这不是很复杂吗？有没有什么更简单更快的方法来处理这个问题呢？(我正在对最多10位的数字使用这些测试)

Answer 1

是的，在应用Pollard Rho之前，你必须检查你分解的数字是不是复合的。如果它是质数，gcd步骤将始终返回1，因为质数总是与其他数共同质数，Pollard Rho将永远运行而没有结果。

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