4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented Jan 2, 2019 at 10:37
  • $\begingroup$ @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 $\endgroup$
    – kelalaka
    Commented Jan 2, 2019 at 19:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented Jan 2, 2019 at 22:43

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.