Ecco un esempio di una versione del sorgente per il fattore GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Include routine sia per la divisione di prova che per il rho di Pollard. A una rapida scansione mi sembra che utilizzi la divisione di prova per trovare alcuni piccoli fattori (fino a circa lg(n)^2 , che in questo caso è circa 4000), quindi Pollard se ciò che rimane non è probabilmente primo. In questo caso è 205432623008947 se ho ragione sui 4000, cioè 35129 * 5847949643 .
Il secondo fattore primo più grande nel tuo esempio è 35129 , e la radice quadrata del più grande è intorno a 76471 . Quindi la divisione di prova da sola sarebbe veloce, dato che deve provare solo circa 25mila candidati.
Gnu coreutils manual informa che è in uso l'algoritmo rho di Pollard.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html