Math on

The first strong pseudoprimes to bases p1... pk

Finding Small Prime Numbers

Note (October 9, 2008): My calculations are incorrect and I am withdrawing my claim to an efficient set of bases. See notes by QU Shun Liang (English) for details, as well as a possible replacement set of bases.

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 ψ9, ψ10, ψ11, and ψ12.

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 ψ2 = 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.)

Jaeschke's Efficient Sets of Bases
2{31, 73}9,080,19115,560,651
2{2, 299417}19,471,03323,464,033
3{2, 7, 61}4,759,123,1418,411,807,377
4{2, 3, 5, 4086253}252,505,670,761736,775,510,329
4{2, 13, 23, 1662803}1,122,004,669,6331,251,470,005,633

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} > 1012).


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 1015, but Bleichenbacher's data shows that they actually work up to 1016.

Livingstone's Efficient Sets of Bases
5{2, 3, 5, 7, 27017}61,995,910,815,54173,288,774,103,581
5{2, 3, 5, 7, 204793}73,288,774,103,58190,022,554,326,251
6{2, 3, 5, 7, 11, 2017}2,402,921,698,865,8272,955,394,617,240,451
7{2, 3, 5, 7, 11, 13, 23}> 1016> 1016
8{2, 3, 5, 7, 11, 13, 17, 23}> 1016> 1016
9{2, 3, 5, 7, 11, 13, 17, 19, 23}> 1016> 1016