Improved performance for factor.

[Ralph Loader]

Hi,

factor in coreutils accepts 64 bit numbers, but can be very slow, e.g.,
try

factor 18446743979220271189

Attached is a patch to use the the Pollard rho factorisation algorithm.

On my ancient dog slow PC it does the above factorisation in about 1/4
seconds instead of 2 minutes.

It factors a number n in time approx O(n**(1/4)) so should be perfectly
OK on any 64 bit number.  [If anyone has a 128 bit machine handy feel
free to let me play :-)].

Ralph.

factor.diff
Description: Text Data