Monday, February 06, 2017

[kxwixtrh] Density of Carmichael numbers

Estimate the number of Carmichael numbers less than x as


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


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.

No comments :