Finding Small Prime Numbers

Recently I've looked into the problem of finding small prime numbers quickly. Of particular interest to me is the method suggested by ψ_k, the smallest strong pseudoprime to the first k bases. Pomerance, Selfridge, and Wagstaff [PSW 1980] calculated the first 4 values of this sequence, and Jaeschke [Jaeschke 1993] calculated the next four. Zhang and Tang [ZT 2003] provide upper bounds for ψ₉, ψ₁₀, ψ₁₁, and ψ₁₂.

The idea is that by testing these small numbers for different bases, efficient primality tests can be made that do not require large stored lists and run quickly in high-performance environments. In order to be most efficient, testing other sets of bases beyond initial primes must be considered. Jaeschke showed that strong probable primes to bases {31, 73} are prime if they are less than 9,080,191, a sixfold improvement from ψ₂ = 1,373,653 which corresponds to the set {2, 3}. The motivation for treating all sets of equal cardinality the same is the fact that run time for the Fermat is not dependant on the size of the base, only the number tested.

A primality test based on these sets has two parts. First, it may check for small prime factors to reduce time wasted on obvious composites. Second, it runs a number of strong Fermat tests on the number, exiting when all hold or when any one fails. The limit for the test may be the lowest composite which passes the strong Fermat test for the set of bases, or the second such number. In the former case, instead of returning true when all tests are passed, it returns the result of an inequality test against the lowest composite passing the tests. (This can easily be generalized to small sets of composites which pass the test, but in my testing this has not appeared efficient.)

The table above is from the last page of Jaeschke's paper (my calculations are in light blue). χ_S = min {n | spsp(S, n)}, in Jaeschke's terminology; I likewise define χ′_S = min {n | spsp(S, n), n > χ_S}. Jaeschke's paper appears to be in error in listing χ_{{2, 3, 5, 4086253}} = 736,775,510,329. Also, I found the exact amount for the last entry (Jaeschke had χ_{{2, 13, 23, 1662803}} > 10¹²).

I have checked all pairs {2, p} for p < 10⁷, all triples {2, 3, p} for p < 10⁸, all triples {2, p, q} with p < q < 10⁵, all triples {3, p, q} with p < q < 10⁵ (the highest was valid only below 3,023,094,619), all quadruples {2, 3, p, q} for p < q < 5·10⁵, and all quadruples {2, p, q, r} for p < q < r < 20000. The 5-tuple {2, 3, 7, 61, 24251} was not discovered by exhaustive search in the same way; it is possible that a more efficient 5-tuple exists with smaller bases.

For these calculations, I used lists of pseudoprimes from Richard Pinch (2-pseudoprimes up to 10¹³), William Galway (2-pseudoprimes up to 10¹⁵), and Daniel Bleichenbacher (2- and 3-strong pseudoprimes up to 10¹⁶). My actual calculations were carried out in C#, C++, and PARI/GP.

Addendum

Arthur Livingstone (pers. comm., April 16, 2007) sent me a list of efficient sets of bases, and with his permission I've added them to this page. The first two are improvements on my five-member set; their χ values are larger though their χ′ values are significantly lower (so they are more useful if you don't test for counterexamples but less if you test for [exactly] one). He tested the last three to 10¹⁵, but Bleichenbacher's data shows that they actually work up to 10¹⁶.

• [Jaeschke 1993] Gerhard Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation 61 (1993), pp. 915–926.
• [PSW 1980] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to 25 · 10⁹, Mathematics of Computation 35 (1980), pp. 1003–1026.
• [ZT 2003] Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Mathematics of Computation 72 (2003), pp. 2085–2097.