mpz_probab_prime_p probability?

[Torbjorn Granlund]

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