Subject: Re: bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)

From: [email-masked] (Niels Möller)
Date: Fri, 07 Sep 2012 10:43:20 +0200

Jim Meyering <[email-masked]> writes:

> The existing code can factor arbitrarily large numbers quickly, as long
> as they have no large prime factors.  We should retain that capability.

My understanding is that most gnu/linux distributions build coreutils
without linking to gmp. So lots of users don't get this capability.

If this is an important feature, maybe one should consider bundling
mini-gmp and use that as a fallback in case coreutils is configured
without gmp (see
http://gmplib.org:8000/gmp/file/7677276bdf92/mini-gmp/README). I would
expect it to be a constant factor (maybe 10) times slower than the real
gmp for numbers up to a few hundred bits (for larger numbers, it gets
much slower due to lack of sophisticated algorithms, but we probably
can't factor them in reasonable time anyway).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.