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?

  • $\begingroup$ Adding in tests can only improve accuracy and increase running time. $\endgroup$ – Charles Jun 21 '13 at 21:02
  • $\begingroup$ I would not expect that, unless the Miller-Rabin test is coded badly. $\endgroup$ – 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.

  • $\begingroup$ Thanks. I see that Pomerance has a few papers on pseudoprimes from around the same time. $\endgroup$ – Brett Hale Jun 19 '13 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.