mpz_probab_prime_p reproducibility

Pierre Chatelier pierre at
Wed Nov 16 07:49:19 UTC 2016


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–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).


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:
> Paul Zimmermann
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at

More information about the gmp-discuss mailing list