mpz_probab_prime_p reproducibility

[Pierre Chatelier]

Hello,

I have checked the source code, and so the answer (in GMP 6.1.1) about reproducibility is no. The miller rabbin tests are done under a gmp_randstate_t, and there is no seed deterministicallly hashed from the number n to test.

I also noticed that the algorithm does not use the "known best subset of <a> to test", as can be found in https://en.wikipedia.org/wiki/Miller–Rabin_primality_test
For instance, every number under 3,317,044,064,679,887,385,961,981 only need 13 reps : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.
This could be implemented in gmp. (The main problem is perhaps to decide, if the user asks for less than 13 reps in mpz_probab_prime_p, if gmp should discard the reps limit set by the user to check at least those known 13 reps).

Regards,

Pierre Chatelier


>       Pierre,
> 
>> 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 ?
> 
> this page has not been updated since 2011 but might still be useful:
> 
> http://www.trnicely.net/misc/mpzspsp.html
> 
> Paul Zimmermann
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss