probable prime tests for gmp

[Paul Leyland]

> 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