Some question about prime numbers and gmp

[Torbjörn Granlund]

Pierre Chatelier <ktd at club-internet.fr> writes:
  
  -what is behaviour to expect for negative integers with
  mpz_probab_prime_p/mpz_nextprime ? Currently, mpz_probab_prime_p seems
  to work as with the absolute value, while nextprime returns 2. Is it a
  behaviour that could change in future releases ?
  
That's hard to answer.

  -mpz_probab_prime_p has the "int reps" parameter, while "mpz_nextprime"
  does not. Does "mpz_nextprime" use internally a default "reps" value ?
  More specifically, it there a minimum "reps" value that can guarantee
  that, for any prime P, mpz_probab_prime_p() won't return any "maybe" for
  any number between P and mpz_nextprime(P) ?
  
This is a probabilistic test, so there is no finite reps value which
gives a prime guarantee.

  -for some values of "reps" (i.e. 25), is there a known number N which is
  the first one for which mpz_probab_prime_p(N) returns "maybe" though the
  known right answer is "No" ? Thus, we could assume that every "maybe"
  answer of mpz_probab_prime_p(..., reps) for numbers less than N is just
  a plain "Yes".
  
It will be hard to find a composite which 25 Miller-Rabin iterations
won't debunk.

Note that the probability (1/4)^reps is a worst case, and may only
happen for numbers of a certain structure.  But (1/4)^25 is still a very
low probability.

  -Let's says that I spend a few hours (days) running gmp, and find that
  the nth prime P (so far in the computation), according to GMP, is indeed
  the real nth prime (according to https://primes.utm.edu for
  instance). Then, I could assume that every "maybe" answer of
  mpz_probab_prime_p() for numbers less than P is just a plain "Yes".  Has
  anybody published such numbers anywhere ?
  
Some people have tabled GMP false positives.  Try something like

  false mpz_probab_prime_p

using your favourite search engine.


Torbjörn
Please encrypt, key id 0xC8601622