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

From: Torbjorn Granlund <[email-masked]>
Date: Sun, 09 Sep 2012 17:21:29 +0200

We made a number of additional changes to the program.

* It now works (again) without longlong.h.  We provide this option for
  code simplicity, at the expensive of performance.

* A new command line option `-w' enables weak primes testing.  This is
  actually often a slowdown since 25 Miller-Rabin tests are currently
  often slower than the default of a combination of Miller-Rabin tests
  and Lucas tests.  It will surely speed up some cases, in particular in
  the GMP range.

* Speedup for prime_p by computing redcify of used bases more
  efficiently.

* Cleanup and more comments.

Pádraig's example should now run at about 40s on his machine.

I believe we could make things about 50% faster for numbers < 2^128,
mainly by improving powm, and by being more clever about how to compute
the powers in Lucas.  We could also speed Pollard rho by reducing the
gcd call frequency.  In the GMP range, there is more headroom.  We can
leave such improvements for the future.

-- 
Torbjörn