# 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.

• The formula with the $2.00743\cdot\ln(2)$ factor remains online despite some ongoing mess, thanks to a webarchive for FIPS 186-4. Importantly, that formula assumes the candidate prime tested is random. – fgrieu Jan 2 '19 at 10:37
• @fgrieu I looked at the Fips, but couldn't find where the constant $2.00743$ occurs. They only say The ideas of paper [1] were applied... But there is no direct result from the article, too – kelalaka Jan 2 '19 at 19:30
• @kelalaka: I found where it occurs (and linked to it), but not how. I tried a few straightforward applications of the formulas in the reference paper, but failed. – fgrieu Jan 2 '19 at 22:43

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})) > 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.