Frobenius pseudoprimes

Grantham, Jon

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

Frobenius pseudoprimes
HTML articles powered by AMS MathViewer

by Jon Grantham PDF

Math. Comp. 70 (2001), 873-891 Request permission

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.

References

William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1–15. MR 866094, DOI 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 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 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 10.1007/3-540-58691-1_{3}6
Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), no. 193, 371–376. MR 1052083, DOI 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 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 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
W. J. Trjitzinsky, General theory of singular integral equations with real kernels, Trans. Amer. Math. Soc. 46 (1939), 202–279. MR 92, DOI 10.1090/S0002-9947-1939-0000092-6
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 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, DOI 10.1007/978-1-4899-3585-4
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 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 10.1016/0304-3975(80)90007-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 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 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 10.1016/0022-314X(80)90084-0
Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703–710. MR 98057, DOI 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 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