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 ?
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
More information about the gmp-discuss
mailing list