# Some question about prime numbers and gmp

Torbjörn Granlund tg at gmplib.org
Sat Dec 20 23:31:49 UTC 2014

```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 ?

-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