mpz_probab_prime_p probability?

Torbjorn Granlund tg at
Mon Jul 9 10:24:27 CEST 2012

Zimmermann Paul <Paul.Zimmermann at> writes:

  on the practical side, Thomas Nicely has a nice web page giving false positives
  for different versions of GMP:
  An updated page from Andreas Höglund for GMP 5.0.1 is available at
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

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.


More information about the gmp-discuss mailing list