[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), (continued)
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Paul Eggert, 2012/09/06
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Niels Möller, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Niels Möller, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Niels Möller, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Paul Eggert, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP),
Torbjorn Granlund <=
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/09
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/10
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/09/07