I'm aware that the Miller–Rabin primality test will claim primality for a composite number with at most a $\frac{1}{4}$ probability for some arbitrary, odd composite $n$ and a random witness $a$ chosen uniformly in the range $[2,n-1)$. What is the actual average chance that that the test falsely claims that the number is prime? How does the chance change as the size of $n$ goes up? How does the chance change if $n$ is not divisible by any small primes up to, say, 2000?
I ask because this paper describes the probability that a composite will survive a number of test rounds. The probability is $p_{k,t}$ with $k$ being the size of the number to be tested in bits and $t$ being the number of rounds to be run. The paper proves that $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, but this inequality is just an upper bound and a separate proof exists to show the much stronger bound $p_{600,1} \le 2^{-75}$. I'd like to find a function with a strong upper bound for $p_{k,t,n}$ with $n$ being trial division against all primes smaller than $n$, but I don't understand the math behind this paper well enough to come up with that.
Table 2 in the paper provides some example lower bounds for $-\lg{p_{k,t}}$:
\begin{array}{c|ccccccccc}
k/t&1&2&3&4&5&6&7&8&9&10\\ \hline
100&5&14&20&25&29&33&36&39&41&44\\
150&8&20&28&34&39&43&47&51&54&57\\
200&11&25&34&41&47&52&57&61&65&69\\
250&14&29&39&47&54&60&65&70&75&79\\
300&19&33&44&53&60&67&73&78&83&88\\
350&28&38&48&58&66&73&80&86&91&97\\
400&37&46&55&63&72&80&87&93&99&105\\
450&46&54&62&70&78&85&93&100&106&112\\
500&56&63&70&78&85&92&99&106&113&119\\
550&65&72&79&86&93&100&107&113&119&126\\
600&75&82&88&95&102&108&115&121&127&133
\end{array}
OpenSSL's key generation appears to assume that this isn't the case, as it increases the number of rounds for larger primes under the illusion that false positive rate somehow impacts the security of the generated prime. Note that this code is used in the prime generation routine, so candidate primes are guaranteed to be uniformly distributed and not subject to worst-case false-positive rate.
From crypto/bn/bn_prime.c:87
:
/*
* Use a minimum of 64 rounds of Miller-Rabin, which should give a false
* positive rate of 2^-128. If the size of the prime is larger than 2048
* the user probably wants a higher security level than 128, so switch
* to 128 rounds giving a false positive rate of 2^-256.
* Returns the number of rounds.
*/
static int bn_mr_min_checks(int bits)
{
if (bits > 2048)
return 128;
return 64;
}