next_prime() frequently returns incorrect results

[GoogleCodeExporter]

You may be aware (though I was surprised) that the next_prime() function 
returns four false primes between 10^7 and 10^8—compare the following results 
to the sequence at http://oeis.org/A006880 :

---
Python 2.7.4 (default, Apr  6 2013, 19:54:46) [MSC v.1500 32 bit (Intel)] on 
win32
Type "copyright", "credits" or "license()" for more information.
>>> import gmpy2
>>> def lazy_primes(n):
                #could be modified to input a lower and upper bound, or none at all
                i = 2
                while i <= n:
                                yield int(i)#no mpz tag
                                i = gmpy2.next_prime(i)

>>> for i in xrange(9):
                print len([p for p in lazy_primes(10**i)])

0
4
25
168
1229
9592
78498
664579
5761459
>>> 

---

Some more testing reveals the false primes in question:

>>> gmpy2.next_prime(2357*7069-1)==2357*7069
True
>>> gmpy2.next_prime(2503*7507-1)==2503*7507
True
>>> gmpy2.next_prime(2131*25561-1)==2131*25561
True
>>> gmpy2.next_prime(4957*14869-1)==4957*14869
True
>>> 

Original issue reported on code.google.com by casevh on 25 Aug 2013 at 3:00

[GoogleCodeExporter]

This has been reported upstream to MPIR. I have patched the version of MPIR 
used to create the 2.0.2 binaries. For the patch to MPIR, see below:

"""

I believe this is caused by the following line in next_likely_prime.c:

    if (mpz_miller_rabin (p, 2, rnd))

The Miller-Rabin test is only repeated twice. IIRC, 25 repeats used to
be the default.

"""

Original comment by casevh on 25 Aug 2013 at 3:02

[GoogleCodeExporter]

GMPY2 2.0.2 has been posted.

Original comment by casevh on 25 Aug 2013 at 5:24

• Changed state: Fixed