mpz_probab_prime_p failure rate

[Décio Luiz Gazzoni Filho]

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

> Alan McFarlane <alan.mcfarlane at gmail.com> 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  
at http://www.trnicely.net/misc/mpzspsp.html

Décio
-------------- 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 : http://gmplib.org/list-archives/gmp-discuss/attachments/20051204/4f43d88d/PGP.bin