Probability Bounds for mpz_probab_prime_p
tg at gmplib.org
Fri Jul 17 08:55:56 CEST 2009
"Emil Stefanov" <emil at berkeley.edu> writes:
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
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".
You need to perform your own analyis of Miller-Rabin wrt your particular
numbers. Then power your estimated error probability to reps...
More information about the gmp-bugs