mpz_probab_prime_p probability?

[Zimmermann Paul]

> >   I was wondering about the probability of composite-ness with the
> >   mpz_probab_prime_p function and the number of reps.
> >  
> >   For the miller-rabin test, if *m *is the number of randomly selected
> >   integers to be used as 'witnesses', the probability of a potential prime
> >   being prime is: 1-(0.5)^m
> >  
> > Not quite.  For certain numbers, 25% of the bases will "bear false
> > witness" of primality.  Most numbers will have *much* fewer liars than
> > 25%.
> > 
> > So for 7 repetitions you'll get 99.994% likelyhood even for the worst
> > numbers.

on the practical side, Thomas Nicely has a nice web page giving false positives
for different versions of GMP: http://www.trnicely.net/misc/mpzspsp.html

An updated page from Andreas Höglund for GMP 5.0.1 is available at
http://www.hoegge.dk/gmp/gmp501.htm

Paul Zimmermann