Frobenius pseudoprimes

Author:
Jon Grantham

Journal:
Math. Comp. **70** (2001), 873-891

MSC (2000):
Primary 11Y11

DOI:
https://doi.org/10.1090/S0025-5718-00-01197-2

Published electronically:
March 1, 2000

MathSciNet review:
1680879

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word “pseudoprime” 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.

- William W. Adams,
*Characterizing pseudoprimes for third-order linear recurrences*, Math. Comp.**48**(1987), no. 177, 1–15. MR**866094**, DOI https://doi.org/10.1090/S0025-5718-1987-0866094-6 - William Adams and Daniel Shanks,
*Strong primality tests that are not sufficient*, Math. Comp.**39**(1982), no. 159, 255–300. MR**658231**, DOI https://doi.org/10.1090/S0025-5718-1982-0658231-9 - W. R. Alford, Andrew Granville, and Carl Pomerance,
*There are infinitely many Carmichael numbers*, Ann. of Math. (2)**139**(1994), no. 3, 703–722. MR**1283874**, DOI https://doi.org/10.2307/2118576 - W. R. Alford, Andrew Granville, and Carl Pomerance,
*On the difficulty of finding reliable witnesses*, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 1–16. MR**1322705**, DOI https://doi.org/10.1007/3-540-58691-1_36 - Steven Arno,
*A note on Perrin pseudoprimes*, Math. Comp.**56**(1991), no. 193, 371–376. MR**1052083**, DOI https://doi.org/10.1090/S0025-5718-1991-1052083-9 - A. O. L. Atkin,
*Intelligent primality test offer*, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 1–11. MR**1486829**, DOI https://doi.org/10.1090/amsip/007/01 - Robert Baillie and Samuel S. Wagstaff Jr.,
*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, DOI https://doi.org/10.1090/S0025-5718-1980-0583518-6 - Daniel M. Gordon,
*Pseudoprimes on elliptic curves*, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR**1024570** - D. M. Gordon and C. Pomerance,
*The distribution of Lucas and elliptic pseudoprimes*, Math. Comp.**57**(1991), 825–838;**60**(1993), 877. ; - J. Grantham,
*Frobenius Pseudoprimes*, dissertation, University of Georgia, 1997. - J. Grantham,
*A Probable Prime Test With High Confidence*, J. Number Theory**72**(1998), 32–47. - J. Grantham,
*There Are Infinitely Many Perrin Pseudoprimes*. - S. Gurak,
*Pseudoprimes for higher-order linear recurrence sequences*, Math. Comp.**55**(1990), no. 192, 783–813. MR**1035934**, DOI https://doi.org/10.1090/S0025-5718-1990-1035934-2 - Richard K. Guy,
*Unsolved problems in number theory*, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR**1299330** - Nathan Jacobson,
*Basic algebra. I*, 2nd ed., W. H. Freeman and Company, New York, 1985. MR**780184** - G. C. Kurtz, Daniel Shanks, and H. C. Williams,
*Fast primality tests for numbers less than $50\cdot 10^9$*, Math. Comp.**46**(1986), no. 174, 691–701. MR**829639**, DOI https://doi.org/10.1090/S0025-5718-1986-0829639-7 - H. W. Lenstra Jr.,
*Primality testing*, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55–77. MR**700258** - Z. Mo and J. P. Jones,
*A new primality test using Lucas sequences*, preprint. - Louis Monier,
*Evaluation and comparison of two efficient probabilistic primality testing algorithms*, Theoret. Comput. Sci.**12**(1980), no. 1, 97–108. MR**582244**, DOI https://doi.org/10.1016/0304-3975%2880%2990007-9 - C. Pomerance,
*Are there counter-examples to the Baillie – 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. - Carl Pomerance,
*On the distribution of pseudoprimes*, Math. Comp.**37**(1981), no. 156, 587–593. MR**628717**, DOI https://doi.org/10.1090/S0025-5718-1981-0628717-0 - Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr.,
*The pseudoprimes to $25\cdot 10^{9}$*, Math. Comp.**35**(1980), no. 151, 1003–1026. MR**572872**, DOI https://doi.org/10.1090/S0025-5718-1980-0572872-7 - Michael O. Rabin,
*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, DOI https://doi.org/10.1016/0022-314X%2880%2990084-0 - Raphael M. Robinson,
*The converse of Fermat’s theorem*, Amer. Math. Monthly**64**(1957), 703–710. MR**98057**, DOI https://doi.org/10.2307/2309747 - A. Rotkiewicz,
*On the pseudoprimes of the form $ax+b$ with respect to the sequence of Lehmer*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**20**(1972), 349–354 (English, with Russian summary). MR**309843** - A. Rotkiewicz,
*On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters $L$, $Q$ in arithmetic progressions*, Math. Comp.**39**(1982), no. 159, 239–247. MR**658229**, DOI https://doi.org/10.1090/S0025-5718-1982-0658229-0 - G. Szekeres,
*Higher order pseudoprimes in primality testing*, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 451–458. MR**1395869**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
11Y11

Retrieve articles in all journals with MSC (2000): 11Y11

Additional Information

**Jon Grantham**

Affiliation:
Institute for Defense Analyses, Center for Computing Sciences, 17100 Science Drive, Bowie, MD 20715

Email:
grantham@super.org

Received by editor(s):
January 6, 1998

Received by editor(s) in revised form:
March 29, 1999

Published electronically:
March 1, 2000

Article copyright:
© Copyright 2000
American Mathematical Society