mpz_nextprime is broken

[Bill Hart]

It looks like mpz_nextprime is completely broken. It declares far too
many composites prime, e.g.

16355809, 393427, 206981, 125563

This broke a whole lot of test code in FLINT-Lite.

Bill.

[Jason Moxham]

I have put a more realistic trial division limit into next_likely_prime , I
had lowered it to test what happened when it actually returned a composite ,
so I suppose it shouldn't of broken any code , just caused it to run slower.

For large numbers failure is so rare that this is tricky to tune , I'll have
to write some special tuning code for it.

[Robert Gerbicz]

2009/10/12 Jason Moxham <ja...@njkfrudils.plus.com>

Or for small numbers use more strong primetests (currently it is using exactly one):

number of fails=234 for 1 strong primetest in [1,10^6] (8 sec)
number of fails=20  for 2 strong primetests in [1,10^6] (13 sec)
number of fails=3   for 3 strong primetests in [1,10^6] (18 sec)

Another option is to use known tables for a true primetest (for "small numbers"), see: http://primes.utm.edu/prove/prove2_3.html

There is even a faster approach for small numbers: precompute all composite numbers up to 2^32 that are strong pseudoprimes for base=2 and 3 (there are about 100 such composites), and use a perfect hash for numbers that survive these two tests (for base=2 and 3) to see if that number is on the list or not.

[Jason Moxham]

yeah , that is the reason for doing the "likely" prime version , we can do
any sort of test that is fast without having to worry about whether it fits the
definition of our probable prime test. As long as the test is fast , and we can
show (with fair confidence) that we are not too much wrong :)




>