linux中factor命令背后的算法是什么？

Question

factor命令打印指定整数NUMBER的素因子.

当我尝试它

factor 12345678912345678912

即使是如此庞大的数字,它也会在工厂内产生.

它使用哪种算法？

Answer 1

Gnu coreutils手册通知正在使用Pollard的rho算法.

http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html

Answer 2

以下是GNU因子源的一个版本的示例:

http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c

它包括试验师和Pollard's rho的惯例.在快速扫描中向我看,好像它使用试验分区来找到一些小因素(lg(n)^2在这种情况下达到约为4000左右),然后Pollard如果剩下的不是可能是素数.在这种情况下,205432623008947如果我对4000是正确的,即35129 * 5847949643.

您示例中的第二大素数因子是35129,并且最大的平方根在附近76471.因此,单独的试验分工会很快,因为它只需要尝试大约2.5万名候选人.