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

[Jim Meyering]

Torbjorn Granlund wrote:

> Jim Meyering <address@hidden> writes:
>
>   > Thanks.  Here's how I've integrated it so far.
>   > This is not ready to push, but rather just to give you an idea
>   > of what's coming.  I'm sure I'll have to adjust things before pushing.
>
>   There have been a few corrections, and I've fleshed out some log entries.
>
>   The following series is ready:
>
>     [PATCH 01/13] build: remove redundant dependency: $(PROGRAMS):
>     [PATCH 02/13] factor: prepare for the new factor program
>     [PATCH 03/13] factor: new implementation; not yet integrated
>     [PATCH 04/13] build: add rules to build the new factor program
>     [PATCH 05/13] factor: improvements from
>     [PATCH 06/13] factor: merge with preexisting factor, integrate
>     [PATCH 07/13] maint: use __builtin_expect only if __GNUC__
>     [PATCH 08/13] maint: syntax-check: add make-prime-list exemptions
>     [PATCH 09/13] factor: 25% speed-up, on output
>     [PATCH 10/13] build: avoid warning about unused macro
>     [PATCH 11/13] maint: mark set-but-not-used variables with
>     [PATCH 12/13] maint: avoid -Wsuggest-attribute=const warning
>     [PATCH 13/13] maint: make-prime-list: do not ignore write failure
>
>   Torbjorn and Niels,
>
>   I'd be happy to include more fine-grained changes to factor.c
>   if you can convert the http://gmplib.org:8000/factoring commits
>   and ChangeLog deltas to git commits where the ChangeLog delta
>   appears in the commit log and passes coreutils' commit-log-checking hook.
>   But that may be more trouble than it's worth.
>
> I think those change logs are not super relevant for the coreutils
> ChangeLog.  "factor.c: Complete rewrite" seem sufficient to me...
>
> Both Niels and I mailed the paperwork to the FSF a week or two ago.
> Have you heard from them?  Snail mail tend to disappear.

Not yet.  I've just asked them.

>   The only missing piece is a NEWS entry.
>   Would one of you please write that?
>
> Sure.  Do you have an example of an old one?  Here is a start:

Here are a few years worth of NEWS entries:

  http://git.sv.gnu.org/cgit/coreutils.git/tree/NEWS

That looks fine.  Thanks.

>   The 'factor' program has been completely rewritten for speed and to
>   add range.  It can now always factor numbers up to 2^128, even without
>   GMP support.  Its speed is from a few times better (for small numbers)
>   to over 10,000 times better (just below 2^64).  The new program also
>   runs a proper prime criterion on found factors, not a probabilistic
>   test.

How about this in place of the final sentence?

                                                    The new program also
    runs a deterministic primality test for each prime factor, not just
    a probabilistic test.

> As you might have spotted from our repo, I and Nisse Möller are working
> on a small Quadratic Sieve ("QS") factorer, for which we have two goals:
>
> (1) offer it as a HAVE_GMP dependent addition to GNU factor
> (2) make a more complex variant intended to be state-of-the-art
>
> QS is one of the most powerful factoring algorithms yet discovered.
> With our implementation, we will be able to factor even the most
> stubborn 128-bit composites within seconds, but with enough patience
> numbers of upp to 300 bits are within reach.
>
> The code is not very large, it will make 'factor' about 30% larger.

That sort of code size increase sounds perfectly
reasonable considering the algorithmic improvements.

> It should factor any 128-bit numbers in around 1 second.  Any 30 bits
> extra take about 10 times more time.

That sounds great.

> I don't think these new developments should hold up a commit of our old
> factor.c developments.

I agree.