Probability Bounds for mpz_probab_prime_p

Emil Stefanov emil at
Fri Jul 17 04:14:31 CEST 2009



I am considering using GNU MP for implementing cryptographic algorithms.
However, the documentation for mpz_probab_prime_p does not provide any
probabilistic bounds on n being composite by chance. Knowing these bounds is
very important to ensure that an algorithm has sufficient cryptographic
strength and is therefore secure.


The documentation mentions that mpz_probab_prime_p uses the Miller-Rabin
probabilistic primality test. Probablity bounds are well known for this
algorithm (see ). It would
be great if the documentation could be updated to explain the correlation
between the "reps" argument and the certainty parameter of the Miller Rabin
primality test. Even better would be to provide a probability bound as a
function of "reps".


Thank you,

Emil Stefanov

More information about the gmp-bugs mailing list