linuxのfactorコマンドの背後にあるアルゴリズムは何ですか？

Question

factorコマンドは、指定された整数NUMBERの素因数を出力します。

私も、このような大きな数字のため

factor 12345678912345678912 

それを試みたとき、それは工場内の結果。

どのアルゴリズムを使用していますか？

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

これは、両方の試験部門及びPollardのrhoためのルーチンを含む：

Answer 1

Gnu coreutils manualにはPollard's rho algorithmが使用されていることが伝えられています。

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

Answer 2

ここGNU因子の源の一のバージョンの例です。試し分けを使っていくつかの小さな要因（最大約lg(n)^2、これは約4000）を見つけたかのように私は素早くスキャンします。残っているものが多分プライムではない場合、Pollard。このケースでは、私が4000程度であれば205432623008947、すなわち35129 * 5847949643です。

例で2番目に大きな素因数は35129であり、最大の平方根は約76471です。試練部門だけでは、約2万5千人の候補者が試用されるため、速くなります。