# Iteration count for (enhanced) Miller-Rabin

In FIPS 186-5 (Digital Signature Standard or DSS) there is a Table B.1 which specifies the minimum number of rounds of Miller-Rabin testing for 1024, 1536 and 2048 bit keys, used for digital signatures. That's already an update to FIPS 186-4 which specified these numbers up to 1536 bits. However there doesn't seem to be a table for any other values over 2048 bit keys.

Table B.1. Minimum number of rounds of M-R testing

Parameters Error probability $$2^{-100}$$ Error probability $$2^{-112}$$
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 140 bits
$$p$$ and $$q$$: 1024 bits
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 32
For $$p$$ and $$q$$: 4
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 38
For $$p$$ and $$q$$: 5
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 170 bits
$$p$$ and $$q$$: 1536 bits
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 27
For $$p$$ and $$q$$: 3
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 41
For $$p$$ and $$q$$: 4
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 200 bits
$$p$$ and $$q$$: 2048 bits
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 22
For $$p$$ and $$q$$: 2
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 44
For $$p$$ and $$q$$: 4

The algorithm for calculating the number of rounds is specified in section C.1 of the same document, but it is relatively complex (especially if you have code for the enhanced M-R test but no code to calculate the values).

Could anyone provide the numbers for other common values for these tests? I'm particularly looking for values for 3072, 4096 and 8192 bit keys.

• Note that the -5 is an update to FIPS 186-4, dated start of February this year, where the table was in section C instead of B. Feb 16 at 15:23
• Do you really mean "to validate an RSA public key"? Well, given a public key, I suppose you might want to make sure it's composite; to do that, a single MR iteration (or Fermat test) will almost certainly be sufficient... Feb 16 at 15:38
• @poncho I'm trying to validate a key using (the arguably old) NIST 800-89 standard, section 5.3.3 (Explicit) Partial Public Key Validation for RSA, e) Not a power of a prime: Check that n is not a power of a prime, i.e., there are no integers b ≥ 2, c ≥ 2 such that n = bc. This can be done by obtaining an output of COMPOSITE AND NOT A POWER OF A PRIME using the enhanced Miller-Rabin primality test in FIPS 186-3. But I guess that's then just a single round for each test? Uh, yes, that must make sense, sorry. I've removed the "public" part from the question. Feb 16 at 15:51

I implemented the algorithm in Appendix C.1 and successfully recomputed table B.1, as well as it's equivalents in FIPS 186-4 (notice that the question's rendition of table B.1 has the probability wrong for the right column, butlast and last box, where that probability should be $$2^{-128}$$ and $$2^{-144}$$ respectively).

The values for 3072 and 4096-bit keys are those in the second and third rows of cells of table B.1. Here is an extension to common key sizes, also covering obsolete ones.

Minimum number of rounds of M-R testing for RSA key generation, assuming trusted random $$p_1$$, $$p_2$$, $$q_1$$, $$q_2$$, $$p$$ and $$q$$, from FIPS 186-5 table B.1 unless otherwise noted

Parameters Error probability $$2^{-100}$$ Progressive error probability
1024-bit public modulus1,2
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 100 bits
$$p$$ and $$q$$: 512 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 38
For $$p$$ and $$q$$: 7
Error probability $$2^{-80}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 28
For $$p$$ and $$q$$: 5
1536-bit public key2,3
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 120 bits
$$p$$ and $$q$$: 768 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 35
For $$p$$ and $$q$$: 5
Error probability $$2^{-96}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 33
For $$p$$ and $$q$$: 5
2048-bit public modulus
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 140 bits
$$p$$ and $$q$$: 1024 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 32
For $$p$$ and $$q$$: 4
Error probability $$2^{-112}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 38
For $$p$$ and $$q$$: 5
3072-bit public modulus
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 170 bits
$$p$$ and $$q$$: 1536 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 27
For $$p$$ and $$q$$: 3
Error probability $$2^{-128}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 41
For $$p$$ and $$q$$: 4
4096-bit public modulus
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 200 bits
$$p$$ and $$q$$: 2048 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 22
For $$p$$ and $$q$$: 2
Error probability $$2^{-144}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 44
For $$p$$ and $$q$$: 4
6144-bit public modulus3
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 230 bits4
$$p$$ and $$q$$: 3072 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 18
For $$p$$ and $$q$$: 2
Error probability $$2^{-160}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 47
For $$p$$ and $$q$$: 3
8192-bit public modulus3
$$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ > 260 bits4
$$p$$ and $$q$$: 4096 bits

For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 16
For $$p$$ and $$q$$: 1
Error probability $$2^{-176}$$
For $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$: 50
For $$p$$ and $$q$$: 3

1 From FIPS 186-4.
2 Obsolete.
3 Extrapolated, using FIPS 186-5 appendix C.1 for the number of rounds.
4 This bound is arbitrary. Further, absent any certification requirement, the only rationale for $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ this large seems to be reuse of code for the generation of $$p$$ and $$q$$ that requires them. While the use of $$p_1$$, $$p_2$$, $$q_1$$ and $$q_2$$ could be justifiable when generating $$2^{40}$$ 1024-bit RSA public keys and requiring infinitesimal probability that any succumbs to a factorization effort concentrating on applying Pollard's $$p-1$$ or Williams's $$p+1$$ to many public moduli rather than ECM, or GNFS to one modulus, that rationale fails for larger public keys.
But perhaps make that 2.