mpz_probab_prime_p failure rate
Décio Luiz Gazzoni Filho
decio at decpp.net
Sun Dec 4 20:38:13 CET 2005
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
More information about the gmp-discuss
mailing list