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

[Jim Meyering]

Torbjorn Granlund wrote:
> I and Niels now would appreciate feedback on the new factor code.
...
> * Our packaging with separate Makefile, outseq.c and ChangeLog was
>   useful during our development.  We don't expect these to be useful
>   in coreutils.  In particular, the slow testing of the 'check' target
>   is probably quite unsuitable for coreutils (but similar but quicker
>   tests would make sense).

I think the tests will be fine, as long as they're separate, and hence
can be parallelized by the default mechanism.  We might want to label
most of them as "expensive", so that they're run only by those who set
RUN_EXPENSIVE_TESTS=yes in their environment.

> * The files probably needed for coreutils are:
>
>   o factor.c -- main factoring code
>   o make-prime-list.c -- primes table generator program
>   o longlong.h -- arithmetic support routines (from GMP)
>
>
> Technical considerations:
>
> * Should we handle numbers >= 2^127?  That would in effect mean
>   merging a current version of GMP's demos/factorize.c into this
>   factor.c, and put that under HAVE_GMP (like in the old factor.c).
>   It should be understood that factoring such large numbers with only
>   Pollard rho is not very feasible.

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

> * We think a --verbose option would be nice, although we don't have
>   one in the present version.  It would output information on
>   algorithm switches and bounds reached.  Opinions?

I think it would be worthwhile, especially to give an idea of what progress
is being made when factoring very large numbers, but hardly something
that need be done now.

E.g., currently this doesn't print much:

    $ M8=$(echo 2^31-1|bc) M9=$(echo 2^61-1|bc) M10=$(echo 2^89-1|bc)
    $ factor --verbose $(echo "$M8 * $M9 * $M10" | bc)
    [using arbitrary-precision arithmetic][trial division (32761)] [is number 
prime?] [pollard-rho (1)]

Ideally it'd print something every second or two.

> Portability caveats:
>
> * We rely on POSIX.1 getchar_unlocked for a performance advantage.
>
> * We have some hardwired W_TYPE_SIZE settings for the code interfacing
>   to longlong.h.  It is now 64 bits.  It will break on systems where
>   uintmax_t is not a 64-bit type.  Please see the beginning of
>   factor.c.

I wonder how many types of systems would be affected.

> Legal caveat:
>
> * Both Niels and Torbjörn are GNU hackers since long.  We do not
>   currently have paperwork in place for coreutils contributions.  This
>   will certainly be addressed.

Thanks.