[kxwixtrh] Density of Carmichael numbers

Estimate the number of Carmichael numbers less than x as

c(x)=x*exp(-k*log(x)*log(log(log(x)))/log(log(x)))

Formula (by Erdos, 1956) is from the Wikipedia page.  There is an unknown constant k, which will be discussed later.

The probability that a number is a Carmichael number is p=c(x)/x.  For the generation of a PGP RSA key, we need 4 primes: 2 primes for the master key, 2 primes for the subkey.  The probability that any of the 4 are Carmichael numbers is approximately 4*p (truncating the binomial expansion).  Primes are half the size of the modulus, so the probability of generating a bad key (at least one Carmichael number) is

pr(n)=4*c(2^(n/2))/(2^(n/2))

We explore various values of that unknown constant k.  It turns out the result is quite sensitive to k.  Empirical calculations on the Wikipedia page up to 10^21 (approximately 2^69) suggest k is around 1.86.

If we estimate k=1.8, then we get the following results.  The probability of failure on (absurdly small) 512-bit keys: 3.56e-44 ; 2048-bit keys = 3.63e-159 ; 4096-bit = 3.54e-303 .

If we far more conservatively estimate k=1.0, then 512-bit = 1.35e-24 ; 2048-bit = 1.76e-88 ; 4096-bit = 1.73e-168 .

The probabilities are probably acceptably small to not worry about accidentally encountering a Carmichael number, though you never know about that constant k.  So Fermat tests are fine, no need for the additional complexity of Miller-Rabin.