mpz_probab_prime_p reproducibility

[David Gillies]

No-one, to the best of my knowledge, has found a pseudoprime that passes fifty M-R trials. For fifty trials the likelihood of a composite number being found prime is < 2^-100, often much (much) less. For 64 bit integers it is known that 12 or 13 witnesses are sufficient. For the sort of primes we might be interested in for, say, RSA, 50 trials is overkill. Eventually, primes become sparse enough that for some given number of trials, the likelihood of picking a pseudoprime at random exceeds the probability of picking a prime. For real-world applications with primes of a few thousand bits at most, this is not a concern.

I don't know about the choice of witnesses in GMP itself and whether it's deterministic or reproducible over different machines. I imagine the implementers would be the ones to elucidate this.

 
> On Nov 11, 2016, at 02:39 , Pierre Chatelier <pierre at chachatelier.fr> wrote:
> 
> Hello,
> 
> I would like to know if two runs of mpz_probab_prime_p(N, 50) for the same number N, on two different machines, trigger the same probabilistic primality tests.
> 
> If this is the case, is there at the current time, a known M value, such that for each integer N < M, the probabilistic answer of mpz_probab_prime_p(N, 50) is exact ?
> In other words, is there any known integer N for which mpz_probab_prime_p(N, 50) is wrong or unsure ?
> 
> Regards,
> 
> Pierre Chatelier
> 
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss