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

[Torbjorn Granlund]

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.

  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:

  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.

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.

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

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

-- 
Torbjörn