Magic Number to calculate number of rounds for M-R in FIPS 186-4 In Fips 186-4, there is an algorithm in Appendix F (at page 117 in my copy of the 2013 version) to calculate the number of rounds of the Miller-Rabin primality test to random bases. 


Does anybody know where the magic number 2.00743 comes from or do I really have to work through the paper Average Case Error Estimates for the Strong Probable Prime Test by I. Damgard et. al
This constant is used to approximate $(\pi(2^k) - \pi(2^{k-1}))^{-1}$, as shown in (4.1) of the Damgard et al. paper:

$$
p_{k,t} \le (\pi(2^k) - \pi(2^{k-1}))^{-1} \sum\nolimits'_{n \in M_k} \bar{\alpha}(n)^t \,.
$$

Most of the formula in the NIST document, between the square brackets, is dealing with the $\bar\alpha$ sum. The left side is dealing with the prime difference approximation.
From Propositon 2 of the Damgard et al. paper, we have

$$
(\pi(2^k) - \pi(2^{k-1})) &gt; 0.71867 \frac{2^k}{k}\,,
$$

from which we can replace $(\pi(2^k) - \pi(2^{k-1}))^{-1}$ by $\frac{1}{0.71867 2^k / k}$ $=$ $1.39145 \cdot k \cdot 2^{-k}$ $=$ $2.00743 \cdot \ln(2) \cdot k \cdot 2^{-k} $. 

The $\ln(2)$ term probably comes from the approximation $\pi(2^k) \approx \frac{2^k}{ \ln(2^k)} = \frac{2^k}{k \cdot \ln(2)}$, as in the proof of Proposition 2.