mpz_probab_prime_p probability?
Zimmermann Paul
Paul.Zimmermann at loria.fr
Mon Jul 9 10:12:37 CEST 2012
> > 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
More information about the gmp-discuss
mailing list