Probability Bounds for mpz_probab_prime_p

[Emil Stefanov]

Hello,

 

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
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test ). 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