probable prime tests for gmp

Jason Moxham
Mon, 4 Nov 2002 17:00:00 +0000

On Monday 04 Nov 2002 4:04 pm, Paul Leyland wrote:
> > 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.
> >
> > We might also want a restartable interface.  For some applications, i=
> > 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 highl=
> misleading.  The more meaningful value is next to impossible to calcula=
> and much, much smaller than the easy value.
> I'll repeat: Miller-Rabin has a 1/4 chance of failure if and only if th=
> argument being tested lies in an extremely small subset of the composit=
> M-R will fail on the other composites with extremely low probability; t=
> set of composites is so dense and the probability of failure so low tha=
t I
> would happily build my personal RSA key out of randomly chosen integers
> which have undergone only one M-R test.

So would I , but a generic interface (if you want a definite answer) must=
either identify these worst cases , or assume the worst. If you dont=20
want/need a definite answer then you could use all sort of conjectures.

I would also use just one M-R test for testing primes of special form , b=
for general numbers ( perhaps I want to test Carmichael type numbers) I w=
want something better , or some theorem which tells me how much better th=
probability really is.

For RSA (which uses random chosen integers) there is a proved probability=
justifies why one M-R test is OK . For any other distribution , 1/4 is th=
best that has been proved . If you willing to go without proof then many=20
things are faster/easier :) eg gmp could use faster FFT's ( not really in=
same league)

Out of interest , are rigourous prime proofs ever worth doing?

> Other tests which do not allow for Carmichael-like cases behave similar=

Has this been proved ? , does say, the lucas prob. prime test have this v=
low prob of failure with randomly chosen ints?

> If you choose a probability argument, which probability do you use?
> Paul