Trial divisions before Miller-Rabin checks? 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 2048th 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}.
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&aring;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}}&lt;{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}$.