bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)
From:
Torbjorn Granlund
Subject:
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)
Date:
Sun, 09 Sep 2012 17:21:29 +0200
User-agent:
Gnus/5.11 (Gnus v5.11) Emacs/22.3 (berkeley-unix)
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