Aquí hay un ejemplo de una versión de la fuente para el factor GNU:
http://www.futuretg.com/FTHumanEvolutionCourse/Source/factor.c
Incluye rutinas tanto para la división de prueba como para la rho de Pollard. En un escaneo rápido, me parece que usa la división de prueba para encontrar algunos factores pequeños (hasta alrededor de lg(n)^2 , que es alrededor de 4000 en este caso), luego Pollard si lo que queda no es probablemente primo. En este caso es 205432623008947 si tengo razón sobre el 4000, es decir, 35129 * 5847949643 .
El segundo factor primo más grande en tu ejemplo es 35129 , y la raíz cuadrada del mayor es alrededor de 76471 . Entonces, la división de prueba sola sería rápida, ya que solo tiene que probar alrededor de 25 mil candidatos.
El manual de Gnu coreutils informa que se está utilizando el algoritmo rho de Pollard.
http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html