{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:40:49Z","timestamp":1776843649431,"version":"3.51.2"},"reference-count":15,"publisher":"American Mathematical Society (AMS)","issue":"234","license":[{"start":{"date-parts":[[2001,2,17]],"date-time":"2001-02-17T00:00:00Z","timestamp":982368000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Define\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \\psi _m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to be the smallest strong pseudoprime to all the first\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n prime bases. If we know the exact value of\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \\psi _m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , we will have, for integers\n \n \n \n \n n<\/mml:mi>\n ><\/mml:mo>\n \n \n \u03c8\n \n <\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n n>\\psi _m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke,\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n m<\/mml:mi>\n <\/mml:msub>\n \\psi _m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are known for\n \n \n \n \n 1<\/mml:mn>\n \n \u2264\n \n <\/mml:mo>\n m<\/mml:mi>\n \n \u2264\n \n <\/mml:mo>\n 8<\/mml:mn>\n <\/mml:mrow>\n 1 \\leq m \\leq 8<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Upper bounds for\n \n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n 9<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \n \u03c8\n \n <\/mml:mi>\n \n 10<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \u00a0and\u00a0<\/mml:mtext>\n \n \n \u03c8\n \n <\/mml:mi>\n \n 11<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n <\/mml:mrow>\n \\psi _9,\\psi _{10} \\text { and } \\psi _{11}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp\u2019s)\n \n \n \n \n n<\/mml:mi>\n ><\/mml:mo>\n \n 10<\/mml:mn>\n \n 24<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n n>10^{24}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to the first ten prime bases\n \n \n \n \n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n \n \u22ef\n \n <\/mml:mo>\n ,<\/mml:mo>\n 29<\/mml:mn>\n ,<\/mml:mo>\n <\/mml:mrow>\n 2, 3, \\cdots , 29,<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n which have the form\n \n \n \n \n n<\/mml:mi>\n =<\/mml:mo>\n p<\/mml:mi>\n \n q<\/mml:mi>\n <\/mml:mrow>\n n=p\\,q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with\n \n \n \n \n p<\/mml:mi>\n ,<\/mml:mo>\n q<\/mml:mi>\n <\/mml:mrow>\n p, q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n odd primes and\n \n \n \n \n q<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n =<\/mml:mo>\n k<\/mml:mi>\n (<\/mml:mo>\n p<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n 4.<\/mml:mn>\n <\/mml:mrow>\n q-1=k(p-1), k=2, 3, 4.<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp\u2019s to both bases 31 and 37. As a result the upper bounds for\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n \n 10<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \\psi _{10}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n \n 11<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \\psi _{11}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for\n \n \n \n \n \n \u03c8\n \n <\/mml:mi>\n \n 12<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \\psi _{12}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke\u2019s and Arnault\u2019s methods are given.\n <\/p>","DOI":"10.1090\/s0025-5718-00-01215-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:46Z","timestamp":1027707466000},"page":"863-872","source":"Crossref","is-referenced-by-count":16,"title":["Finding strong pseudoprimes to several bases"],"prefix":"10.1090","volume":"70","author":[{"given":"Zhenxiang","family":"Zhang","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,2,17]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"173","DOI":"10.2307\/2006975","article-title":"On distinguishing prime numbers from composite numbers","volume":"117","author":"Adleman, Leonard M.","year":"1983","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2307\/2118576","article-title":"There are infinitely many Carmichael numbers","volume":"139","author":"Alford, W. R.","year":"1994","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-58691-1_36","article-title":"On the difficulty of finding reliable witnesses","author":"Alford, W. R.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"issue":"209","key":"4","doi-asserted-by":"publisher","first-page":"355","DOI":"10.2307\/2153340","article-title":"Rabin-Miller primality test: composite numbers which pass it","volume":"64","author":"Arnault, F.","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"203","key":"5","doi-asserted-by":"publisher","first-page":"29","DOI":"10.2307\/2152935","article-title":"Elliptic curves and primality proving","volume":"61","author":"Atkin, A. O. L.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","unstructured":"W.Bosma and M.P. van der Hulst, Primality proving with cyclotomy, thesis, Univ. of Amsterdam, 1990."},{"issue":"177","key":"7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.2307\/2007877","article-title":"Implementation of a new primality test","volume":"48","author":"Cohen, H.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"165","key":"8","doi-asserted-by":"publisher","first-page":"297","DOI":"10.2307\/2007581","article-title":"Primality testing and Jacobi sums","volume":"42","author":"Cohen, H.","year":"1984","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"9","series-title":"A Wiley-Interscience Publication","isbn-type":"print","volume-title":"Primes of the form $x^2 + ny^2$","author":"Cox, David A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0471506540"},{"key":"10","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-1779-2","volume-title":"A classical introduction to modern number theory","volume":"84","author":"Ireland, Kenneth F.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0387906258"},{"issue":"204","key":"11","doi-asserted-by":"publisher","first-page":"915","DOI":"10.2307\/2153262","article-title":"On strong pseudoprimes to several bases","volume":"61","author":"Jaeschke, Gerhard","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/S0022-0000(76)80043-8","article-title":"Riemann\u2019s hypothesis and tests for primality","volume":"13","author":"Miller, Gary L.","year":"1976","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0304-3975(80)90007-9","article-title":"Evaluation and comparison of two efficient probabilistic primality testing algorithms","volume":"12","author":"Monier, Louis","year":"1980","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"issue":"151","key":"14","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.2307\/2006210","article-title":"The pseudoprimes to 25\u22c510\u2079","volume":"35","author":"Pomerance, Carl","year":"1980","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"15","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","article-title":"Probabilistic algorithm for testing primality","volume":"12","author":"Rabin, Michael O.","year":"1980","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01215-1\/S0025-5718-00-01215-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01215-1\/S0025-5718-00-01215-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:35:39Z","timestamp":1776724539000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01215-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,2,17]]},"references-count":15,"journal-issue":{"issue":"234","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0025-5718-00-01215-1"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01215-1","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2000,2,17]]}}}