mpz_probab_prime_p failure rate

Décio Luiz Gazzoni Filho decio at
Sun Dec 4 20:38:13 CET 2005

On Dec 4, 2005, at 12:41 PM, Torbjorn Granlund wrote:

> Alan McFarlane <alan.mcfarlane at> writes:
>   Are there any web sites which list the first few failures of
>   mpz_probab_prime_p for a given iteration count?
> I am not aware of any "failures" (which I assume would be cases
> where a compostive number is returned as prime).
> There aren't any "Carmichael numbers" for the Miller-Rabin test.

This could possibly be misread by the OP, so I'll add a bit:

There aren't indeed any Carmichael numbers (which are numbers for  
which Fermat's test always fails, unless the base used shares a  
factor with the integer being tested), but there are numbers which  
could fail for many different bases; for instance, Arnault's number  
is a strong pseudoprime to all prime bases less than 200. The  
probability of finding one of those is exceedingly small though; far  
smaller than hardware failures, bit flips due to cosmic rays and so on.

FWIW, Thomas Nicely maintains a list of mpz_probab_prime_p failures  

-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: This is a digitally signed message part
Url :

More information about the gmp-discuss mailing list