Sla*_*eek 3 algorithm primes factorization
每当我使用Pollard Rho分解方法对数字进行因子分解时,是否有必要在Pollard Rho分解之前检查它的素数？如果是,那么我必须实施Miller Rabin的素性测试或任何素性测试,每次我想要考虑任何数字而且我必须要处理强伪赝,这不是很复杂吗？有没有简单而又更快的方法来处理这个问题？(我在最多10位数的数字上使用这些测试)
是的,在申请Pollard Rho之前,您必须检查您要保留的数字是否为复合数.如果它是素数,则gcd步骤将始终返回1,因为素数始终与其他所有数字共同,并且Pollard Rho将永远运行而没有结果.
对于最多十位数的数字,Pollard Rho不是必需的.简单的试验分区将足够快,因为您只需要小于100000的素数,并且只有9592个.