-----BEGIN PGP SIGNED MESSAGE-----

What estimates exist for the density of large Carmichael numbers, say 1000 bits long?

I'm not sure off hand - maybe Ray can try to check the source of his formula. Carmichael numbers must be square free and the product of at least three primes... I seem to remember a formula for the distribution of square free integers, but can't quite remember it...

test? Are other probability tests like Miller-Rabin any more provably likely to detect these?

Well Phil, you are in luck! Miller-Rabin isn't fooled by Carmichael numbers. There still is a chance for failure, but it doesn't depend on the input (i.e. there are no bad inputs for Miller-Rabin like there are for pseudoprime testing). Failure depends on how many iterations you perform (n iterations = 2^-n chance of failure) and the values of the base you choose. For example, in Miller-Rabin, the Carmichael number 561 is exposed to be composite by choosing a base of 7. I'm familiar with two other primality testing algorithms (I'm no number theory wiz so there are probably more): Lucas' and Lehmer's. Well, Lehmer's method is a modification of Lucas' method. They both are slow, but have the advantage of being true. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLaoM/IOA7OpLWtYzAQEXPQQAy1110rgCUzLtKoaTsWvGCujq3fWD7Ppz A+/2b4NmR9+YmqHl63kb9zKU1/KOfDVXsmE7o0beyRQzSNGzj2I5yEUrnz0IzBLt cy4ooiE3ED/jBBc01MBYhm5v3s9dIMJNXbsw7mBSBasqzEvHHpjH8dnGZA8QXhYT fKTlU7rKa0o= =XgrZ -----END PGP SIGNATURE-----