**Two Methods to Calculate the Required Number of**

**Rounds of Miller-Rabin Testing**

Currently, NIST recommends that when testing a candidate prime for use
in DSA and RSA signature schemes, the following tests are performed:

> When testing the RSA *p* and *q* primes, 8 rounds of Miller-Rabin
> (M-R) are performed followed by a single Lucas test. For the smaller
> primes$p_{1}$,$p_{2}$, $q_{1}$, and $q_{2}$, that are used as part of
> the assurance that the *p* and *q* primes are "strong", 50
> Miller-Rabin tests are required. These recommendations are in
> accordance with theAmerican National Standard (ANS) X9.31 standard.
>
> For the DSA primes *p* and *q*, 50 M-R tests are required by Federal
> Information Processing Standard (FIPS) 186-2. The reason for the large
> number of the required tests is that if an error occurs and either *p*
> or *q* turns out to be a composite number, then this error will be
> experienced system-wide.

NIST is taking a fresh look at these requirements and preparing the new
recommendations for the number of M-R tests after considering comments
that were submitted for the draft of FIPS 186-3. After searching
available literature on primality testing, two alternative methods are
presented below; NIST strongly recommends Method 1, rather than Method
2.

**1. Method 1**. **(Recommended)**

Apply the ideas of paper \[1\] to estimate *p ~k,t\ ~*, the probability
that an odd *k*-bit integer that passes *t* rounds of M-R testing is
actually composite. The probability $p_{k,t}$ is understood as the ratio
of the number of odd composite numbers of a binary length *k* that pass
*t* rounds of M-R testing (with randomly generated bases) to the total
number of odd integers of binary length *k*. This is equivalent to
assuming that candidates selected for testing will be chosen uniformly
at random from the entire set of odd *k*-bit integers. From the
perspective of a party charged with the responsibility of generating a
*k*-bit prime, the objective is to determine a value of *t* such that
$p_{k,t}$ is no greater than an acceptably small target
value$p_{t\text{arg}\text{et}}$.

From \[1\], it is possible to compute an upper bound for $p_{k,t}$ as a
function of *k* and *t*. Inversing this, one can compute an upper bound
for *t* as a function of *k* and $p_{t\text{arg}\text{et}}$, the maximum
allowed probability of accidentally generating a composite number. The
algorithm for computing *t* is as follows:

> For *t* = 1, 2 ... (up to some stopping value needed to be able to
> stop when no number of rounds of M-R would suffice)
>
> For *M* = 3, 4 ... $\left\lfloor 2\sqrt{k - 1} - 1 \right\rfloor$
>
> Compute $p_{k,t}$ as in (2).
>
> If $p_{k,t} \leq p_{t\text{arg}\text{et}}$
>
> Accept *t* (1)
>
> Stop
>
> Endif
>
> Endfor
>
> Endfor

Here, *k* is the bit length of the candidate primes, and (2) is as
follows:

> $p_{k,t} = 2\text{.}\text{00743} \cdot \text{ln}(2) \cdot k \cdot 2^{- k}\left\lbrack 2^{k - 2 - \text{Mt}} + \frac{8(\pi^{2} - 6)}{3}2^{k - 2}\sum_{m = 3}^{M}{2^{m - (m - 1)t}\sum_{j = 2}^{m}\frac{1}{2^{j + (k - 1)j}}} \right\rbrack$
> . (2)

Armed with this expression for *t*, the following methodologies are
proposed for testing the DSA and RSA candidate primes.

**1.1 Generating DSA Primes**

For the DSA, one has to exercise the maximum possible care when
generating the primes. The same primes *p* and *q* are used by many
parties, since they are domain parameters. This means that any weakness
that these numbers may possess would affect multiple users. It also
means that the primes are not generated very often; typically, the
entire system uses the same set of parameters. Therefore, in this case,
some additional care is called for.

With this in mind, it may be too optimistic to assume that conditions
allow one to simply compute *t* according to (1) and (2). One may want
to be more cautious and either include some additional testing (beyond
the M-R tests) or use a more conservative estimate of the error
probabilities associated with the M-R tests. This approach leads to the
following strategy: either (A) use the number of M-R tests as calculated
above and follow them with a single Lucas test, as defined, for example,
in ANS X9.31, or (B) base the choice of *t* on a different formulation
of the probability of an error occurring in the M-R testing, leading to
a more conservative recommendation.

One approach of type (B) would be to adopt the viewpoint of the majority
of system users, who have no part in generating the (supposed) prime,
but who must rely upon its primality for their security. Such parties
may be concerned that the candidates for M-R testing have been selected
in a fashion that deviates significantly from the uniform distribution
-- which was assumed when determining *t* according to (1) and (2). In
cases where the selection process could be unusually biased in some way,
it is important to minimize the probability that a composite number will
survive testing. It can be shown that for any *k*-bit odd composite
number (regardless of how it was selected), the probability that it will
pass *t* rounds of M-R testing with randomly chosen bases is less
than$4^{- t}$ (although this is not a particularly tight bound).
Selecting *t* such that 4*^-t^* ≤ *p~target~* is equivalent to choosing
*t* ≥ log~2~(*p~target~*)/2. To insure that a composite number has a
probability no greater than *p~target~* of surviving the M-R tests, one
can set the number of rounds at *t* = --log~2~(*p~target~)*/2. Even if
the method of selecting candidates were so biased that it offered
nothing but composite numbers for testing, one can reasonably expect
that it would take at least 1/ *p~target~* attempts (which is greater
than 4*^t^* ) before a composite number would slip through the *t*-round
M-R testing process.

**WARNING:** As the discussion above illustrates, one must take care
when using the phrase "error probability" in connection with the
recommended number of rounds of M-R testing. The probability that a
composite number survives *t* rounds of Miller-Rabin testing is
[not]{.underline} the same as *p ~k,t\ ~*, which is the probability that
a number surviving *t* rounds of Miller-Rabin testing is composite.
Ordinarily, the latter probability is the one that should be of most
interest to a party responsible for generating primes, while the former
may be more important to a party responsible for validating the
primality of a number generated by someone else. However, for
sufficiently large *k* (e.g., *k* ≥ 51), it can be shown that *p ~k,t~*
≤ 4*^-t^* -- under the same assumptions concerning the selection of
candidates as those made to obtain formula (2). (See \[1\].) In such
cases, *t* = --log~2~(*p~target~)*/2 rounds of Miller-Rabin testing can
be used both in generating and validating primes, with *p~target~*
serving as an upper bound on both the probability that the generation
process yields a composite number and the probability that a composite
number would survive an attempt to validate its primality.

This leads us to the following recommended values for *t* when selecting
the DSA primes *p* and *q*. Please note that the sizes of *p* and *q*
are chosen in such a way that the probability ($2^{- \text{80}}$, or
$2^{- \text{112}}$, or $2^{- \text{128}}$) of having the signature
forged when *p* and *q* are known to be prime is similar to the
probability of mistakenly generating a composite number.

+---------------------+-----------------------+------------------------+
|                     | Number of M-R tests   | Number of M-R when     |
|                     | only                  | followed by one Lucas  |
|                     |                       | test                   |
+---------------------+-----------------------+------------------------+
| Error probability:  | 40                    | For *p* -- 3           |
| $2^{- \text{80}}$   |                       |                        |
|                     |                       | For *q* -- 19          |
| *p* size - 1024     |                       |                        |
| bits, *q* size -    |                       |                        |
| 160 bits            |                       |                        |
+---------------------+-----------------------+------------------------+
| Error probability:  | 56                    | For *p* -- 3           |
| $2^{- \text{112}}$  |                       |                        |
|                     |                       | For *q* -- 24          |
| *p* size - 2048     |                       |                        |
| bits, *q* size -    |                       |                        |
| 224 bits            |                       |                        |
+---------------------+-----------------------+------------------------+
| Error probability:  | 64                    | For *p* -- 2           |
| $2^{- \text{128}}$  |                       |                        |
|                     |                       | For *q* -- 27          |
| *p* size - 3072     |                       |                        |
| bits, *q* size -    |                       |                        |
| 256 bits            |                       |                        |
+---------------------+-----------------------+------------------------+

**Table 1.** Recommended number of Miller-Rabin tests when generating
primes *p* and *q* for use in DSA, as determined by Method 1, using
strategies (A) and (B).

**1.2 Generating Primes for RSA Signatures**

When generating primes for the RSA signature algorithm, it is still very
important to reduce the probability of errors in the M-R testing
procedure. However, if a composite number survives the testing process,
the consequences of the error may be less dramatic than in the case of
generating DSA domain parameters, since the composite number is used by
only one entity to generate its key pair. If an extremely unlikely event
occurs, and one of the$p_{1}$, $p_{2}$, $q_{1}$, $q_{2}$ primes turns
out to be composite, then there is still a high probability that the
corresponding RSA prime will satisfy the requisite conditions. If the
*p* or *q* value generated for some user turns out to be composite, the
problem will not go undiscovered for long, since it is almost certain
that signatures generated by that user will not be verifiable.

NIST therefore proposes that it is not necessary to use the Lucas test
when testing$p_{1}$, $p_{2}$, $q_{1}$, and $q_{2}$for primality. When
testing *p* and *q*, in general, it is sufficient to have the number of
the Miller-Rabin tests as derived from (1) and (2). One always has the
option to follow this with a single Lucas test.

**1.2.1. Sizes of Primes and Error Probabilities**

The sizes of *p* and *q* that are recommended for use in RSA signature
algorithms are 512, 1024 and 1536 bits. They yield modulus sizes of
1024, 2048 and 3072 bits, and security strengths of 80, 112 and 128
bits, correspondingly. Hence, it makes sense to match the number of
rounds of Miller-Rabin testing to *p~target~* values of 2^-80^, 2^-112^,
and 2^-128^, respectively.

The sizes of $p_{1}$, $p_{2}$, $q_{1}$, and $q_{2}$are generally chosen
to be 21 to 40 bits larger than the security strength of the RSA
signature algorithm, based on the size of *p* and *q*. This is
consistent with the original choice of parameters in AN X9.31, where the
*p* and *q* would yield 80 bits of security and the smaller primes were
101 to 120 bits in length.

The following numbers of tests are therefore recommended.

+---------------------+------------------+-----------------------------+
|                     | M-R tests only   | Optionally                  |
+---------------------+------------------+-----------------------------+
| Error probability:  | $p_{1}$,         | *p*, *q* -- 5 M-R plus one  |
| $2^{- \text{80}}$   | $p_{2}$,         | Lucas test                  |
|                     | $q_{1}$, $q_{2}$ |                             |
| $p_{1}$, $p_{2}$,   | -- 28            |                             |
| $q_{1}$, $q_{2}$ -  |                  |                             |
| 101 to 120 bits     | *p*, *q* -- 5    |                             |
|                     |                  |                             |
| *p*, *q* size --    |                  |                             |
| 512 bits, *n* --    |                  |                             |
| 1024 bits           |                  |                             |
+---------------------+------------------+-----------------------------+
| Error probability:  | $p_{1}$,         | *p*, *q* -- 5 M-R plus one  |
| $2^{- \text{112}}$  | $p_{2}$,         | Lucas test                  |
|                     | $q_{1}$, $q_{2}$ |                             |
| $p_{1}$, $p_{2}$,   | -- 39            |                             |
| $q_{1}$, $q_{2}$ -  |                  |                             |
| 133 to 152 bits     | *p*, *q* -- 5    |                             |
|                     |                  |                             |
| *p*, *q* size --    |                  |                             |
| 1024 bits, *n* --   |                  |                             |
| 2048 bits           |                  |                             |
+---------------------+------------------+-----------------------------+
| Error probability:  | $p_{1}$,         | *p*, *q* -- 4 M-R plus one  |
| $2^{- \text{128}}$  | $p_{2}$,         | Lucas test                  |
|                     | $q_{1}$, $q_{2}$ |                             |
| $p_{1}$, $p_{2}$,   | -- 44            |                             |
| $q_{1}$, $q_{2}$ -  |                  |                             |
| 149 to 168 bits     | *p*, *q* -- 4    |                             |
|                     |                  |                             |
| *p*, *q* size --    |                  |                             |
| 1536 bits, *n* --   |                  |                             |
| 3072 bits           |                  |                             |
+---------------------+------------------+-----------------------------+

**Table 2.** Recommended number of Miller-Rabin tests when generating
primes for use in RSA digital signatures, as determined by (1) and (2)
above.

**1.3. Special Case of Security Strength of 100 Bits**

In the previous subsection, the most plausible interpretation of the
intent of ANS X9.31 when choosing the prime sizes and the error
probabilities is presented. The sizes of *p* and *q* determine the
strength of the signature algorithm and this, in turn, determines the
choice of the target error probability in the Miller-Rabin tests and, as
a result, the required number of these tests.

However, the same ANS X9.31 standard could be interpreted as demanding
that the Miller-Rabin error probability always be 2^-100^ . This is
because it required 50 Miller- Rabin tests for $p_{1}$, $p_{2}$,
$q_{1}$, and $q_{2}$, and one can argue that it was derived from the
estimate 4*^-t^* ≤ *p~target~*. NIST computed the required numbers of
Miller-Rabin tests for the 2^-100^ error probability. The number of
tests is based on the algorithm (1) and (2). The sizes of *p* and *q*
are, as before, 512, 1024, or 1536. The sizes of$p_{1}$, $p_{2}$,
$q_{1}$, and $q_{2}$are either 101 to 120 bits as in ANS X9.31, or 121
to 140 bits, to be consistent with the log~2~(*p~target~*)+21 to
log~2~(*p~target~*)+40 approach.

The following statements summarize the requirements when *p~target~* =
$2^{- \text{100}}$.

> For$p_{1}$, $p_{2}$, $q_{1}$, $q_{2}$ - 101 to 120 bits, 38
> Miller-Rabin tests are required.
>
> For$p_{1}$, $p_{2}$, $q_{1}$, $q_{2}$ - 121 to 140 bits, 35
> Miller-Rabin tests are required.
>
> For *p*, *q* -- 512 bits, 7 Miller-Rabin tests are required.
>
> For *p*, *q* -- 1024 bits, 4 Miller-Rabin tests are required.
>
> For *p*, *q* -- 1536 bits, 3 Miller-Rabin tests are required.

As before, when testing *p* and *q* for primality, the Miller-Rabin
tests may optionally be followed by a single Lucas test.

**2. Method 2. (Not Recommended)**

An even more aggressive approach to estimating the required number of
M-R has been proposed in \[1\]. It is based on the same interpretation
of the error probability$p_{k,t}$ as used in Method 1 to arrive at the
estimate given by (2) (which, in itself, is rather aggressive). In order
to obtain a tighter bound on$p_{k,t}$, an optimization is performed over
the values of not just one integer parameter M, as in (1), but over a
large array of parameters, some of which are real-valued. The details
are outlined in \[2\], but some are omitted, so it is necessary to trust
that the authors performed their optimization the right way.

The resulting recommendations for *t* are stated in \[1\] for only a few
pairs of

(*k*, $p_{t\text{arg}\text{et}})$. One can also find this table of the
calculated values of *t* in \[3\], Fact 4.48. Without the full details
stated in any of the papers, it is not possible to apply their analysis
to the different values of the target error probability. Therefore, NIST
does not recommend choosing this method and provides it in this paper
only for completeness. NIST would even argue against using this method
when the M-R tests are followed by a Lucas test. This is especially true
if the DSA candidate primes are tested.

**References**

\[1\] Damgard, I., Landrock, P., and Pomerance, C. "Average Case Error
Estimates for the Strong Provable Prime Test," Mathematics of
Computation, v. 61, No, 203, pp. 177-194, 1993.

\[2\] Kim, S.H. and Pomerance, C., "*The Probability that a Random
Probable Prime is Composite,*" Mathematics of Computation, v.53, No.
188, pp. 721-741, 1989.

\[3\] Menezes, A.,J., van Oorschot, P.,C., and Vanstone, S.A., "Handbook
of Applied Cryptography," CRC Press, 1997.