The figure I have for the Carmichael numbers is x^(.1), where .1 is approximate. Ray has the exponent at 2/7. The exact one doesn't matter so much, because compared to the density of primes (x/ln x), these are both extremely small. The chance of picking a Carmichael number is very small. But that's not the relevant density. The problem with RSAREF's prime testing is that it will find pseudoprimes base 2. Carmichael numbers are pseudoprimes to any base, but that's unneeded for the RSAREF test. What is needed is the density of pseudoprimes base 2. I don't know that figure. I don't know that anybody does. I would really suggest that someone with access to Mathematica or Maple do an experiment to find out how many non-primes the RSAREF algorithm passes. Carmichael numbers do not, generally, pass the Miller-Rabin test. Some might; I'll bet it's an open question. Eric