# probable prime tests for gmp

**Paul Leyland
**
pleyland@microsoft.com

*Mon, 4 Nov 2002 08:04:25 -0800*

>* We want a generic function, but with a better interface than the
*>* current mpz_probab_prime_p. A probability argumetn is much better
*>* that a repeat count.
*>*=20
*>* We might also want a restartable interface. For some applications, it
*>* might be useful to find a few likely primes, then determine with much
*>* higher probability that certain numbers are really prime.
*
Sigh. I've been trying to get over the idea that there is no single =
probability for most probable prime tests. The value which is easy to =
calculate (e.g. the infamous 1/4 for Miller-Rabin) is correct but highly =
misleading. The more meaningful value is next to impossible to =
calculate and much, much smaller than the easy value.
I'll repeat: Miller-Rabin has a 1/4 chance of failure if and only if the =
argument being tested lies in an extremely small subset of the =
composites. M-R will fail on the other composites with extremely low =
probability; this set of composites is so dense and the probability of =
failure so low that I would happily build my personal RSA key out of =
randomly chosen integers which have undergone only one M-R test.
Other tests which do not allow for Carmichael-like cases behave =
similarly.
If you choose a probability argument, which probability do you use?
Paul