mpz_probab_prime_p probability?
Torbjorn Granlund
tg at gmplib.org
Mon Jul 9 10:24:27 CEST 2012
Zimmermann Paul <Paul.Zimmermann at loria.fr> writes:
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
I am not sure I'd call their results "practical"...
The numbers they study are presumably of the form pq where (p-1)/(q-1) =
s, where s is a small integer. For s = 2 we get the worst case
Miller-Rabin false witness ratio of 1/4.
For uniformly distributes random integers, such numbers pq are rare, of
course.
We have looked into an improved set if probabilistic prime testing
functions, where we identify numbers like the one above, and then as a
result can run considerably fewer Miller-Rabin cycles.
--
Torbjörn
More information about the gmp-discuss
mailing list