# Probability of 2 as a liar in the SPRP test - Miller-Rabin

I've used number-theoretic results for p(k, t) (e.g., DLP) to create a utility, mrtab, that generates the Miller-Rabin iterations (as a k-bit threshold table) required to satisfy a given error-probability; $2^{-128}$ is the default.

Still, many sources suggest an independent 2-SPRP test, since (2) is a witness for most composites. Modular exponentiation of (2) can be implemented efficiently, and it typically saves RNG entropy by not starting with a randomized base.

According to Burthe, the average least witness is 2. The first composite that passes the 2-SPRP test is 2047. I've tabled the proportion of k-bit composites that pass the 2-SPRP test:

11 bits : 2.66666667e-03
12 bits : 2.60078023e-03
13 bits : 6.31313131e-04
14 bits : 6.20347395e-04
15 bits : 1.51975684e-04
16 bits : 2.99535720e-04
17 bits : 2.58693965e-04
18 bits : 1.09515031e-04
19 bits : 9.03489276e-05
20 bits : 6.71113915e-05
21 bits : 5.76877848e-05
22 bits : 3.19298864e-05
23 bits : 2.35109375e-05
24 bits : 1.71167930e-05


Of course, these are anecdotal results, but an independent 2-SPRP test, prior to the Miller-Rabin test with (t) trials clearly lowers the error probability of p(k,t).

What I haven't been able to find are any upper-bound estimates for (2) as a (strong) liar. In particular, for a randomly selected k-bit number. Are there any sources for this? Or suggestions?

• Adding in tests can only improve accuracy and increase running time. – Charles Jun 21 '13 at 21:02
• I would not expect that, unless the Miller-Rabin test is coded badly. – Charles Jun 21 '13 at 22:27

In that paper, Burthe cites the following result of Pomerance: the number of base-2 pseudoprimes less than $x$ is at most $x \exp({-}\log x \log\log\log x/2\log\log x)$ when $x$ is large. This expression is thus an upper bound for the number of base-2 strong pseudoprimes as well. (In fact, Pomerance's result holds with 2 replaced by any fixed $b$.)
So the probability that a randomly selected $k$-bit number is a base-2 strong pseudoprime is at most $2^{-k \log\log k/2\log k}$ when $k$ is large.