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

Question

factor命令打印指定整数的素因数。

当我尝试的时候

factor 12345678912345678912

即使对于如此大的数字，它也是在工厂内部产生的。

使用的是哪种算法？

Answer 1

Gnu手册通知正在使用Pollard's rho algorithm。

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

Answer 2

下面是GNU factor的一个版本的源代码示例：

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

它包括审判部门和Pollard的rho的例程。在我看来，快速扫描就好像它使用试除法来找到一些小因子(最高约为lg(n)^2，在本例中约为4000 )，如果剩下的可能不是-质数，则使用Pollard。在这种情况下，如果我对4000的估计是正确的，那就是205432623008947，即35129 * 5847949643。

在您的示例中，第二大素数因子是35129，最大素数的平方根在76471附近。因此，光是审判部门就会很快，因为它只需要尝试大约25000名候选人。