mpz_probab_prime_p() failures

[Sisyphus]

>
> FWIW, Thomas Nicely maintains a list of mpz_probab_prime_p failures
> at http://www.trnicely.net/misc/mpzspsp.html
>

That's interesting. For some reason I thought that mpz_probab_prime_p() did
a fermat test (base of 2) after the trial divisions - yet nearly all of
those numbers are reported composite by such a fermat test. (Not sure where
I got that notion from. On re-reading the GMP docs I can't find any
reference to fermat tests wrt mpz_probab_prime_p).

It's a little disconcerting to me that mpz_netxprime() also throws up the
very same composites as being prime. (It doesn't start getting it right
until we get down to 25366866661.)

For the little extra overhead, wouldn't it be worth having the bases of the
miller-rabin test pseudorandomly determined, rather than pre-set ?
Just using C's rand() function seeded with some combination of (last few
digits of) timestamp and pid would suffice (I think). This would then be in
keeping with the way that probable primality tests *ought* to be conducted -
and the above webpage becomes irrelevant - which is a pity, as it's a nice
piece of work :-)

Cheers,
Rob