Frobenius pseudoprimes

Grantham, Jon

doi:10.1090/S0025-5718-00-01197-2

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