Average case error estimates for the strong probable prime test

Abstract:

Consider a procedure that chooses k-bit odd numbers independently and from the uniform distribution, subjects each number to t independent iterations of the strong probable prime test (Miller-Rabin test) with randomly chosen bases, and outputs the first number found that passes all t tests. Let ${p_{k,t}}$ denote the probability that this procedure returns a composite number. We obtain numerical upper bounds for ${p_{k,t}}$ for various choices of k, t and obtain clean explicit functions that bound ${p_{k,t}}$ for certain infinite classes of k, t. For example, we show ${p_{100,10}} \leq {2^{ - 44}},{p_{300,5}} \leq {2^{ - 60}},{p_{600,1}} \leq {2^{ - 75}}$ , and ${p_{k,1}} \leq {k^2}{4^{2 - \sqrt k }}$ for all $k \geq 2$. In addition, we characterize the worst-case numbers with unusually many "false witnesses" and give an upper bound on their distribution that is probably close to best possible.