Subject: bug#42269: Remove non-GMP code from coreutils factor.c

From: [email-masked] (Torbjörn Granlund)
Date: Wed, 08 Jul 2020 23:46:38 +0200

[email-masked] (Niels Möller) writes:

  I'm really not that familiar with state of the art factoring, but I'd
  guess pollard rho is a bad algorithm choice for that range, and one
  ought to use, e.g., some variant of the quadratic sieve.

Let me modify that statement somewhat.

Pollars rho is suitable for finding small factors of any size
composites.  Small here might mean about < 2^64.

Any factoring effort should start with trial division, then some rounds
of Pollard rho, then perhaps some EC rounds.  Only after that and when a
remaining cofactor is non-prime, QS is to be rolled out.

That could sound like the GMP code of coreutils factor is great for
factoring really large numbers.  It is, but only for smooth huge
numbers.

If we ever get crazy enough to consider QS for coreutils factor, its
current GMP Pollard rho code would become part of a general factoring
engine for numbers > 2^127.

-- 
Torbjörn
Please encrypt, key id 0xC8601622