{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:22:43Z","timestamp":1776784963551,"version":"3.51.2"},"reference-count":18,"publisher":"American Mathematical Society (AMS)","issue":"253","license":[{"start":{"date-parts":[[2006,9,15]],"date-time":"2006-09-15T00:00:00Z","timestamp":1158278400000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n J. Browkin defined in his recent paper (Math. Comp.\n 73<\/bold>\n (2004), pp.\u00a01031\u20131037) some new kinds of pseudoprimes, called Sylow\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprimes and elementary Abelian\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprimes. He gave examples of strong pseudoprimes to many bases which are not Sylow\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprime to two bases only, where\n \n \n \n \n p<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n p=2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n or\n \n \n \n 3<\/mml:mn>\n 3<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In this paper, in contrast to Browkin\u2019s examples, we give facts and examples which are unfavorable for Browkin\u2019s observation to detect compositeness of odd composite numbers. In Section 2, we tabulate and compare counts of numbers in several sets of pseudoprimes and find that most strong pseudoprimes are also Sylow\n \n \n \n 2<\/mml:mn>\n 2<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprimes to the same bases. In Section 3, we give examples of Sylow\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprimes to the first several prime bases for the first several primes\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We especially give an example of a strong pseudoprime to the first six prime bases, which is a Sylow\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprime to the same bases for all\n \n \n \n \n p<\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n {<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n 5<\/mml:mn>\n ,<\/mml:mo>\n 7<\/mml:mn>\n ,<\/mml:mo>\n 11<\/mml:mn>\n ,<\/mml:mo>\n 13<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n p\\in \\{2,3,5,7,11,13\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In Section 4, we define\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to be a\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -\n fold<\/italic>\n Carmichael Sylow pseudoprime<\/italic>\n , if it is a Sylow\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -pseudoprime to all bases prime to\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for all the first\n \n \n \n k<\/mml:mi>\n k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n smallest odd prime factors\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of\n \n \n \n \n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We find and tabulate all three\n \n \n \n 3<\/mml:mn>\n 3<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -fold Carmichael Sylow pseudoprimes\n \n \n \n \n ><\/mml:mo>\n \n 10<\/mml:mn>\n \n 16<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n >10^{16}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . In Section 5, we define a positive odd composite\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n to be a\n Sylow uniform pseudoprime to bases<\/italic>\n \n \n \n \n \n b<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n ,<\/mml:mo>\n \n b<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n b_1,\\ldots ,b_k<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , or a Syl-upsp\n \n \n \n \n (<\/mml:mo>\n \n b<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n ,<\/mml:mo>\n \n b<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n (b_1,\\ldots ,b_k)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for short, if it is a Syl\n \n \n \n \n \n p<\/mml:mi>\n <\/mml:msub>\n _p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -psp\n \n \n \n \n (<\/mml:mo>\n \n b<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n ,<\/mml:mo>\n \n b<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n (b_1,\\ldots ,b_k)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n for all the first\n \n \n \n \n \n \u03c9\n \n <\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n \\omega (n-1)-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n small prime factors\n \n \n \n p<\/mml:mi>\n p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n of\n \n \n \n \n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n \n \n \u03c9\n \n <\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \\omega (n-1)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is the number of distinct prime factors of\n \n \n \n \n n<\/mml:mi>\n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n n-1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We find and tabulate all the 17 Syl-upsp\n \n \n \n \n (<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n 5<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n (2,3,5)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n \u2019s\n \n \n \n \n ><\/mml:mo>\n \n 10<\/mml:mn>\n \n 16<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n >10^{16}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and some Syl-upsp\n \n \n \n \n (<\/mml:mo>\n 2<\/mml:mn>\n ,<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n 5<\/mml:mn>\n ,<\/mml:mo>\n 7<\/mml:mn>\n ,<\/mml:mo>\n 11<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n (2,3,5,7,11)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n \u2019s\n \n \n \n \n ><\/mml:mo>\n \n 10<\/mml:mn>\n \n 24<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n >10^{24}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Comparisons of effectiveness of Browkin\u2019s observation with Miller tests to detect compositeness of odd composite numbers are given in Section 6.\n <\/p>","DOI":"10.1090\/s0025-5718-05-01775-8","type":"journal-article","created":{"date-parts":[[2005,11,16]],"date-time":"2005-11-16T10:22:35Z","timestamp":1132136555000},"page":"451-460","source":"Crossref","is-referenced-by-count":3,"title":["Notes on some new kinds of pseudoprimes"],"prefix":"10.1090","volume":"75","author":[{"given":"Zhenxiang","family":"Zhang","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2005,9,15]]},"reference":[{"issue":"2","key":"1","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","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","unstructured":"D. Bleichenbacher, Efficiency and Security of Cryptosystems Based on Number Theory, ETH Ph.D. dissertation 11404, Swiss Federal Institute of Technology, Zurich, 1996."},{"key":"4","isbn-type":"print","volume-title":"A course in computational number theory","author":"Bressoud, David","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/1930190107"},{"issue":"246","key":"5","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1090\/S0025-5718-03-01617-X","article-title":"Some new kinds of pseudoprimes","volume":"73","author":"Browkin, Jerzy","year":"2004","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9316-0","volume-title":"Prime numbers","author":"Crandall, Richard","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0387947779"},{"issue":"204","key":"7","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":"8","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"},{"key":"9","unstructured":"R. G. E. Pinch, The Carmichael numbers up to 10\u00b9\u2076, preprint, 1998. \\url{http:\/\/www.chalcedon.demon.co.uk\/carpsp.html}."},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/10722028_30","article-title":"The pseudoprimes up to 10\u00b9\u00b3","author":"Pinch, Richard G. E.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"issue":"151","key":"11","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":"12","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"},{"key":"13","unstructured":"Anton Stiglic, The PRIMES is in P little FAQ, \\url{http:\/\/crypto.cs.mcgill.ca\/ stiglic\/PRIMES_{P}_{F}AQ.html}"},{"issue":"234","key":"14","doi-asserted-by":"publisher","first-page":"863","DOI":"10.1090\/S0025-5718-00-01215-1","article-title":"Finding strong pseudoprimes to several bases","volume":"70","author":"Zhang, Zhenxiang","year":"2001","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"240","key":"15","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1090\/S0025-5718-02-01424-2","article-title":"A one-parameter quadratic-base version of the Baillie-PSW probable prime test","volume":"71","author":"Zhang, Zhenxiang","year":"2002","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"250","key":"16","doi-asserted-by":"publisher","first-page":"1009","DOI":"10.1090\/S0025-5718-04-01693-X","article-title":"Finding \ud835\udc36\u2083-strong pseudoprimes","volume":"74","author":"Zhang, Zhenxiang","year":"2005","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"244","key":"17","doi-asserted-by":"publisher","first-page":"2085","DOI":"10.1090\/S0025-5718-03-01545-X","article-title":"Finding strong pseudoprimes to several bases. II","volume":"72","author":"Zhang, Zhenxiang","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"18","first-page":"414","article-title":"The great prime number record races","volume":"51","author":"Ziegler, G\u00fcnter M.","year":"2004","journal-title":"Notices Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9920","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01775-8\/S0025-5718-05-01775-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01775-8\/S0025-5718-05-01775-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:34:11Z","timestamp":1776782051000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-253\/S0025-5718-05-01775-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9,15]]},"references-count":18,"journal-issue":{"issue":"253","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["S0025-5718-05-01775-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-05-01775-8","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":[[2005,9,15]]}}}