{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T04:25:17Z","timestamp":1777091117850,"version":"3.51.4"},"reference-count":27,"publisher":"American Mathematical Society (AMS)","issue":"234","license":[{"start":{"date-parts":[[2001,3,1]],"date-time":"2001-03-01T00:00:00Z","timestamp":983404800000},"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":"<p>The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word \u201cpseudoprime\u201d in them. Examples include pseudoprimes, Euler pseudoprimes, strong pseudoprimes, Lucas pseudoprimes, strong Lucas pseudoprimes, extra strong Lucas pseudoprimes and Perrin pseudoprimes. Though these tests represent a wealth of ideas, they exist as a hodge-podge of definitions rather than as examples of a more general theory. It is the goal of this paper to present a way of viewing many of these tests as special cases of a general principle, as well as to re-formulate them in the context of finite fields. One aim of the reformulation is to enable the creation of stronger tests; another is to aid in proving results about large classes of pseudoprimes.<\/p>","DOI":"10.1090\/s0025-5718-00-01197-2","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:46Z","timestamp":1027707466000},"page":"873-891","source":"Crossref","is-referenced-by-count":18,"title":["Frobenius pseudoprimes"],"prefix":"10.1090","volume":"70","author":[{"given":"Jon","family":"Grantham","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,3,1]]},"reference":[{"issue":"177","key":"1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2007869","article-title":"Characterizing pseudoprimes for third-order linear recurrences","volume":"48","author":"Adams, William W.","year":"1987","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"159","key":"2","doi-asserted-by":"publisher","first-page":"255","DOI":"10.2307\/2007637","article-title":"Strong primality tests that are not sufficient","volume":"39","author":"Adams, William","year":"1982","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"3","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":"4","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":"193","key":"5","doi-asserted-by":"publisher","first-page":"371","DOI":"10.2307\/2008548","article-title":"A note on Perrin pseudoprimes","volume":"56","author":"Arno, Steven","year":"1991","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"6","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/amsip\/007\/01","article-title":"Intelligent primality test offer","author":"Atkin, A. O. L.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"issue":"152","key":"7","doi-asserted-by":"publisher","first-page":"1391","DOI":"10.2307\/2006406","article-title":"Lucas pseudoprimes","volume":"35","author":"Baillie, Robert","year":"1980","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"8","isbn-type":"print","first-page":"290","article-title":"Pseudoprimes on elliptic curves","author":"Gordon, Daniel M.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/3110117916"},{"key":"9","doi-asserted-by":"publisher","first-page":"202","DOI":"10.2307\/1989920","article-title":"General theory of singular integral equations with real kernels","volume":"46","author":"Trjitzinsky, W. J.","year":"1939","journal-title":"Trans. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"10","unstructured":"J. Grantham, Frobenius Pseudoprimes, dissertation, University of Georgia, 1997."},{"key":"11","doi-asserted-by":"crossref","unstructured":"J. Grantham, A Probable Prime Test With High Confidence, J. Number Theory 72 (1998), 32\u201347.","DOI":"10.1006\/jnth.1998.2247"},{"key":"12","unstructured":"J. Grantham, There Are Infinitely Many Perrin Pseudoprimes."},{"issue":"192","key":"13","doi-asserted-by":"publisher","first-page":"783","DOI":"10.2307\/2008447","article-title":"Pseudoprimes for higher-order linear recurrence sequences","volume":"55","author":"Gurak, S.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"14","series-title":"Problem Books in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-3585-4","volume-title":"Unsolved problems in number theory","author":"Guy, Richard K.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942890","edition":"2"},{"key":"15","isbn-type":"print","volume-title":"Basic algebra. I","author":"Jacobson, Nathan","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/0716714809","edition":"2"},{"issue":"174","key":"16","doi-asserted-by":"publisher","first-page":"691","DOI":"10.2307\/2008007","article-title":"Fast primality tests for numbers less than 50\u22c510\u2079","volume":"46","author":"Kurtz, G. C.","year":"1986","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"17","isbn-type":"print","first-page":"55","article-title":"Primality testing","author":"Lenstra, H. W., Jr.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/906196248X"},{"key":"18","unstructured":"Z. Mo and J. P. Jones, A new primality test using Lucas sequences, preprint."},{"issue":"1","key":"19","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"},{"key":"20","unstructured":"C. Pomerance, Are there counter-examples to the Baillie \u2013 PSW primality test?, Dopo Le Parole aangeboden aan Dr. A. K. Lenstra (H. W. Lenstra, Jr., J. K. Lenstra and P. Van Emde Boas, eds.), Amsterdam, 1984."},{"issue":"156","key":"21","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/2007448","article-title":"On the distribution of pseudoprimes","volume":"37","author":"Pomerance, Carl","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"151","key":"22","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":"23","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":"24","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2307\/2309747","article-title":"The converse of Fermat\u2019s theorem","volume":"64","author":"Robinson, Raphael M.","year":"1957","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"key":"25","first-page":"349","article-title":"On the pseudoprimes of the form \ud835\udc4e\ud835\udc65+\ud835\udc4f with respect to the sequence of Lehmer","volume":"20","author":"Rotkiewicz, A.","year":"1972","journal-title":"Bull. Acad. Polon. Sci. S\\'{e}r. Sci. Math. Astronom. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-4117","issn-type":"print"},{"issue":"159","key":"26","doi-asserted-by":"publisher","first-page":"239","DOI":"10.2307\/2007635","article-title":"On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters \ud835\udc3f, \ud835\udc44 in arithmetic progressions","volume":"39","author":"Rotkiewicz, A.","year":"1982","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"27","isbn-type":"print","first-page":"451","article-title":"Higher order pseudoprimes in primality testing","author":"Szekeres, G.","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/9638022752"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01197-2\/S0025-5718-00-01197-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01197-2\/S0025-5718-00-01197-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:35:40Z","timestamp":1776724540000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01197-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3,1]]},"references-count":27,"journal-issue":{"issue":"234","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0025-5718-00-01197-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01197-2","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,3,1]]}}}