linuxalgorithmcommandprime-factoringfactorization

what is the algorithm behind the factor command in linux?

The factor command prints the prime factors of specified integer NUMBER.

When I tried it

factor 12345678912345678912

even for such big numbers, it results within milliseconds.

Which algorithm is it using?

Solution

  • Gnu coreutils manual informs that Pollard's rho algorithm is being used.

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