probable prime tests for gmp

[Jason Moxham]

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=
t
> > 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=
y
> misleading.  The more meaningful value is next to impossible to calcula=
te
> 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=
e
> argument being tested lies in an extremely small subset of the composit=
es.=20
> M-R will fail on the other composites with extremely low probability; t=
his
> 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=
=20
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=
ut=20
for general numbers ( perhaps I want to test Carmichael type numbers) I w=
ould=20
want something better , or some theorem which tells me how much better th=
e=20
probability really is.

For RSA (which uses random chosen integers) there is a proved probability=
 that=20
justifies why one M-R test is OK . For any other distribution , 1/4 is th=
e=20
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=
 the=20
same league)

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

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

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

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