k | ψ_{k} |
---|---|

1 | 2,047 |

2 | 1,373,653 |

3 | 25,326,001 |

4 | 3,215,031,751 |

5 | 2,152,302,898,747 |

6 | 3,474,749,660,383 |

7 | 341,550,071,728,321 |

8 | 341,550,071,728,321 |

9 | ≤3,825,123,056,546,413,051 |

10 | ≤3,825,123,056,546,413,051 |

11 | ≤3,825,123,056,546,413,051 |

12 | ≤318,665,857,834,031,151,167,461 |

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

#S | S | χ_{S} | χ′_{S} |
---|---|---|---|

1 | {377687} | 5,329 | 9,881 |

2 | {31, 73} | 9,080,191 | 15,560,651 |

2 | {2, 299417} | 19,471,033 | 23,464,033 |

3 | {2, 7, 61} | 4,759,123,141 | 8,411,807,377 |

4 | {2, 3, 5, 4086253} | 252,505,670,761 | 736,775,510,329 |

4 | {2, 13, 23, 1662803} | 1,122,004,669,633 | 1,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}} > 10^{12}).

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^{15}, but Bleichenbacher's data shows that they actually work up to 10^{16}.

#S | S | χ_{S} | χ′_{S} |
---|---|---|---|

5 | {2, 3, 5, 7, 27017} | 61,995,910,815,541 | 73,288,774,103,581 |

5 | {2, 3, 5, 7, 204793} | 73,288,774,103,581 | 90,022,554,326,251 |

6 | {2, 3, 5, 7, 11, 2017} | 2,402,921,698,865,827 | 2,955,394,617,240,451 |

7 | {2, 3, 5, 7, 11, 13, 23} | > 10^{16} | > 10^{16} |

8 | {2, 3, 5, 7, 11, 13, 17, 23} | > 10^{16} | > 10^{16} |

9 | {2, 3, 5, 7, 11, 13, 17, 19, 23} | > 10^{16} | > 10^{16} |

- [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

,^{9}*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.