mpz_nextprime deficiencies

Heinz van Saanen van.saanen at aon.at
Sun Sep 11 10:30:50 CEST 2011


Hello,

mpz_nextprime is convenient, fast - and fails a bit too often. E.g:


#include <gmp.h>

int main (void) {

     mpz_t p;

     // p+1 is NOT prime !!!
     mpz_init_set_str(p, "189452997113368438678230", 10);

     while (1) {
         mpz_nextprime(p, p);
         if ( mpz_probab_prime_p(p, 14) == 0 )
             gmp_printf("A false mpz_nextprime : %Zd\n", p);
     }

     return 0;
}


You may avoid this with a "counterpart" to mpz_probab_prime_p:

void mpz_nextprime (mpz t rop, mpz t op, int reps)

In the source the MR-repetitions for nextprime() are hard-coded as 10, 
what seems a bit inflexible. For the manual I would suggest a hint on 
both probab_prime_p() and nextprime() probabilities. For pure 
Miller-Rabin it is 4^(-reps). Both GMP-functions perform a bit better as 
they do additional tests. But this would give an order of magnitude at 
least.

A short note to mpq_t. For sure you avoid bloating the interface. But 
especially for rationals this really would be no luxury:

void mpq_reciprocal (mpq_t rop, mpq_t op)


-- Heinz van Saanen


More information about the gmp-bugs mailing list