I and Niels Möller have written a suggested replacement for coreutils
factor.c.  It fixes a number of issues with the current code:

(1) Much faster trial division code (> 10x) based on a small table of
    prime inverses.  Still, the new code doesn't perform lots of trial
    dividing.

(2) Pollard rho code using Montgomery representation for numbers < 2^64.
    (We consider extending this to 128 bits.)  Not dependent on GMP.

(3) Lucas prime proving code instead of probablitic Miller-Rabin primes
    testing.

(4) SQUFOF code, which might be included depending on performance
    issues.

(5) Replacement GMP code (#if HAVE_GMP) that also includes Lucas proving
    code.

The new code is faster than the current code:

Old:
  seq `pexpr 2^64-1000` `pexpr 2^64-1` | time factor >/dev/null
  524.57 user

New:
  seq `pexpr 2^64-1000` `pexpr 2^64-1` | time ./factor >/dev/null
  0.05 user

For smaller number ranges, the improvements are currently much more
modest, as little as 2x in some cases.

The code should be ready within a few weeks.

-- 
Torbjörn