Trial divisions before Miller-Rabin checks?

Question

I'm trying to understand prime number generation (more correctly, the primality checking) as described in Handbook of Applied Cryptography.

The context is circa pages 145 - 150, and specifically Table 4.4 (p. 148). The table presents (k,t) pairs, where 'k' is the number of bits in the candidate and 't' is the number of Miller-Rabin iterations that keeps the error rate below $2^{-80}$. From the table (partial shown below):

  k  |  t
=====|=====
 100 |  27
 200 |  15
 400 |   7
 450 |   6
 550 |   5
 650 |   4
 850 |   3
1300 |   2
2050 |   2

However, the discussion surrounding the table notes that "one is usually willing to accept an error probability of $({1\over2})^{80}$ when using Algorithm 4.44". Algorithm 4.44 (p. 146) states to use trial division to rule out low hanging fruit (sic).

But according to Note 4.45 (p. 146), Algorithm 4.44 bounds the trial division based on B, where B is based on the time it takes to perform a modular exponentiation versus time required to rule out a small prime by trial division.

If the "proper" number of trial divisions are not performed (for some definition of "proper"), then error rate may not be as expected. I'm reading that from the discussion on page 165, where its suggested to select 't' such that its equal to ${1\over2}\cdot\lg(k)$. Using this formula, it appears a 1024-bit candidate needs 5 or 6 Miller-Rabins test, and not the 2 or 3 advertised in Table 4.4.

Question: how many trial divisions against a table of primes should be performed before moving to Miller-Rabin? In essence, I'm asking how large the prime table used in trial division should be.

Is it enough to test all primes up to (and including) 17863? 17863 happens to be the 2048^th prime.

Related Question: is the acceptable error rate still $2^{-80}$?

(Sorry about the tag. It does not appear there are tags for random-numbers, primality-testing, trial-division or Miller-Rabin)

---

EDIT (JUN-17-2014): The reason I asked was OpenSSL and Crypto++ random number generation. I did not want ot taint answers with too much context.

OpenSSL uses a prime table up to 17863 and Miller-Rabin according to Table 4.4. Crypto++ uses a prime table up to 32719 and either 1 or 10 round Miller-Rabin.

The OpenSSL source files of interest are openssl/crypto/bn/bn.{h|c}, and the Crypto++ source files of interest are cryptopp/nbtheory.{h|cpp}.

Answer 1

Update: the formula actually on page 165 in chapter 4 of the HAC is: $t=\lceil{1\over2}\cdot\lg n\rceil$, where $\lg$ is the base-2 logarithm; that is $t=\lceil{1\over2}\cdot k\rceil$; and that crude estimate asks for 512 Miller-Rabin tests for 1024-bit primes, not 5 or 6 tests as stated in the question based on the erroneous $t=\lceil{1\over2}\cdot\lg k\rceil$, or 3 tests as in Table 4.4. That crude formula $t=\lceil{1\over2}\cdot\lg n\rceil$ is based on the fact that a MR round has odds at most $1\over4$ to let a composite pass, is usable in practice with often acceptable speed penalty, but is way overkill for primes of size suitable for cryptographic keys.

The authoritative academic reference on the number of Miller-Rabin tests is this paper: Ivan Damgård, Peter Landrock, and Card Pomerance, Average Case Error Estimates for the Strong Probable Prime Test, Mathematics of Computation, v. 61, No, 203, pp. 177-194, 1993. That's reference [300] in the HAC, and used to derive their Table 4.4.

The authoritative normative reference, which also cites the previous paper, is FIPS 186-4 appendix F.1, with even more down-to-earth prescriptions in the context of generating FIPS 186-4 RSA keys in tables C.2 and C.3, reproduced at the end of this answer.

All the references above consider that $n$ being tested is a random odd integer of specified bit size. Using trial division by small odd primes combined with Miller-Rabin slightly increases the confidence we can have that the number tested is prime compared to MR alone, but that is usually neglected. The main reason to perform such trial division is as a speedup: most of the integers tested are going to be composite, we want to rule them out as fast as possible, and early trial division achieves that.

As an example suitable in many cases of cryptographic interest on modern desktop CPUs: in order to test if some large random odd $n$ is prime, noticing that $k=3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29$ is less than $2^{32}$, we can compute $r=n\bmod k$ efficiently using hardware 64-bit by 32-bit division; then skip Miller-Rabin if $\gcd(r,k)\ne1$. That leaves only ${{2\cdot4\cdot6\cdot10\cdot12\cdot16\cdot18\cdot22\cdot28}\over{3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29}}<{1\over3}$ of candidates to be tested by MR, and thus speeds up things by a factor of over 3 on many platforms (including most where MR is slow). We can do more trial division, but with severely diminishing returns (the speed-up is by a factor at most 1.14 for division by $31\cdot37\cdot41\cdot43\cdot47$). The above technique with $k=2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$ is easy to code efficiently on most 32-bit embedded CPUs, already gives a speedup of about 2.5, and might be good enough. Experiment can be used to determine the optimum; trial division by the first 2047 odd primes will be beyond that point if there's a half-decent modexp.

Note: it is notoriously hard to validate primality-testing code, especially in a black-box setup. MR is popular because it is simple thus relatively easy to proofread, but caution! With large parameters, it is almost impossible to ever reach the second MR test, at least if the witness used is random! We can easily craft test cases that pass trial division, but ideally these should also be Carmichael numbers if we want a chance to catch some improper MR variations, and I do not know if the extensive literature on generation of large Carmichael numbers provides that.

---

In practice, in the context of RSA, one can do (very) little trial division, following by a number of MR tests according to the following table:

In this table, error probability (like $2^{-80}$ in the first box) is for the guaranteed residual odds of accepting a composite for any of the 6 (pseudo)primes involved in the RSA key generation process: $p$, $q$, and shorter intermediary primes $p_1$, $p_2$, $q_1$, $q_2$ such that $p\equiv1\pmod{p_1}$, $p\equiv-1\pmod{p_2}$, $q\equiv1\pmod{q_1}$, $q\equiv-1\pmod{q_2}$.

Answer 2

The table from the Handbook of Applied Cryptography is computed for candidate primes taken as odd integers. This is equivalent to using trial division by $2$ only. Note that section 4.48 specifies that:

Using more advanced techniques, the upper bounds on $p_{k,t}$ given by Fact 4.48 have been improved. These upper bounds arise from complicated formulae which are not given here.

So the table lists $t$ values which are smaller than would can be derived from the formulas in the Handbook.

Using more primes for trial division can only decrease the risk of mistakenly decreeing an integer prime where it is not; by doing trial division beyond the simple parity test, you may only incur the risk of doing "too many" Miller-Rabin tests. However, this does not matter much. Indeed, let's consider that you want to generate a 1000-bit prime. I have sampled about 200000 random odd 1000-bit integers (bits 0 and 999 forced to 1, the 998 others being randomly generated). It appears that:

• Of these 200000 random odd integers, 22950 were not a multiple of any prime in the 1 to 17864 range; i.e. trial division would let only 1 in 8.71 candidates go the Miller-Rabin stage.
• Of these 22950 candidates, only 561 were actually prime. That's about one in 41. For non-primes, it is expected that, with very high probability, one round of Miller-Rabin will detect them as such (if 3 rounds suffices to reach $2^{-80}$, then one round already has a very decent probability of detection).

So if you decide to declare a 1000-bit integer prime when it passes $t$ rounds of Miller-Rabin, and you do trial division up to 17863 (the first 2048-bit primes), then you can expect to have to perform an average of $40 + t$ Miller-Rabin rounds. Therefore, the impact of $t$ on performance is, at best, minor: difference between $t = 3$ and $t = 6$ really is the difference between $43$ and $46$, i.e. less than 7%.

---

Therefore, there is little point in trying to optimize the $t$ value. The values given in table 4.4 may actually be overkill, especially if coupled with trial division, since they are meant to ensure the $2^{-80}$ probability even with only a parity check. Using $t = \lceil(\lg k) / 2\rceil$ is a bigger overkill even -- but not enough to actually matter. The overwhelming majority of your CPU bill will be spent on non-primes, and will be independent of whatever value you choose for $t$.

As for trial division, it is a question of balance between the cost of the divisions, vs the cost of Miller-Rabin. My measures show that using 2048 primes indeed reduces the number of Miller-Rabin invocations: only one in 8.7 odd candidates will survive the trial divisions. However, such divisions are not free: they have to be computed, and the primes must also be stored somewhere (this can be an issue on embedded systems with low ROM size). Extra primes for trial divisions are also a matter of diminishing returns: using 25 primes (all primes up to 100) for trial divisions already removes one in 4.2 odd candidates. The optimal trade-off depends on the relative costs of trial divisions and Miller-Rabin on your platform; since part of the cost is ROM size, it can be challenging to reach a definitive conclusion (it depends on the overall application context).

---

Edit: "trial division" by some small primes can be considerably sped up if you integrate it into the candidate generation process. Namely, you randomly choose $k$ modulo $2$, $3$, $5$, $7$... up to $23$ (to keep values in 32-bit words), taking care to avoid $0$ as value for any of these small mods. Then you build up your 1024-bit candidate $k$ with the Chinese Remainder Theorem. This candidate building, and the Miller-Rabin rounds, can be computed without using any actual division anywhere: this is a good thing if you use a platform which lacks a hardware division opcode.