linux中的factor命令背後的算法是什麼？

Question

factor命令打印指定整數NUMBER的主要因子。

當我試圖

factor 12345678912345678912 

即使是這些大的數字，它導致鋼廠內。

它使用哪種算法？

Answer 1

Gnu coreutils手冊通知Pollard's rho algorithm正在使用中。

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

Answer 2

下面的源GNU因子的一個版本的一個示例：

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

它包括兩個試除法和波拉德的RHO例程。在快速掃描中看起來好像它使用審判部門來尋找一些小因素（高達約lg(n)^2，在這種情況下約爲4000），然後是Pollard，如果剩下的不是最重要的。在這種情況下，如果我對4000，即35129 * 5847949643是正確的，那麼就是205432623008947。

您例子中的第二大素因子是35129，最大的平方根大約是76471。所以只有審判部門會很快，因爲它只需要嘗試約25000名候選人。