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.

1. William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1–15. MR 866094, https://doi.org/10.1090/S0025-5718-1987-0866094-6
2. William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255–300. MR 658231, https://doi.org/10.1090/S0025-5718-1982-0658231-9
3. 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, https://doi.org/10.2307/2118576
4. 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, https://doi.org/10.1007/3-540-58691-1_36
5. Steven Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), no. 193, 371–376. MR 1052083, https://doi.org/10.1090/S0025-5718-1991-1052083-9
6. 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
7. Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, https://doi.org/10.1090/S0025-5718-1980-0583518-6
8. Daniel M. Gordon, Pseudoprimes on elliptic curves, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 290–305. MR 1024570
9. Daniel M. Gordon and Carl Pomerance, The distribution of Lucas and elliptic pseudoprimes, Math. Comp. 57 (1991), no. 196, 825–838. MR 1094951, https://doi.org/10.1090/S0025-5718-1991-1094951-8
10. J. Grantham, Frobenius Pseudoprimes, dissertation, University of Georgia, 1997.
11. J. Grantham, A Probable Prime Test With High Confidence, J. Number Theory 72 (1998), 32-47. CMP 98:17
12. J. Grantham, There Are Infinitely Many Perrin Pseudoprimes.
13. S. Gurak, Pseudoprimes for higher-order linear recurrence sequences, Math. Comp. 55 (1990), no. 192, 783–813. MR 1035934, https://doi.org/10.1090/S0025-5718-1990-1035934-2
14. 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
15. Nathan Jacobson, Basic algebra. I, 2nd ed., W. H. Freeman and Company, New York, 1985. MR 780184
16. G. C. Kurtz, Daniel Shanks, and H. C. Williams, Fast primality tests for numbers less than 50⋅10⁹, Math. Comp. 46 (1986), no. 174, 691–701. MR 829639, https://doi.org/10.1090/S0025-5718-1986-0829639-7
17. 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
18. Z. Mo and J. P. Jones, A new primality test using Lucas sequences, preprint.
19. Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, https://doi.org/10.1016/0304-3975(80)90007-9
20. 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.
21. Carl Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), no. 156, 587–593. MR 628717, https://doi.org/10.1090/S0025-5718-1981-0628717-0
22. Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff Jr., The pseudoprimes to 25⋅10⁹, Math. Comp. 35 (1980), no. 151, 1003–1026. MR 572872, https://doi.org/10.1090/S0025-5718-1980-0572872-7
23. Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, https://doi.org/10.1016/0022-314X(80)90084-0
24. Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703–710. MR 98057, https://doi.org/10.2307/2309747
25. A. Rotkiewicz, On the pseudoprimes of the form 𝑎𝑥+𝑏 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
26. A. Rotkiewicz, On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with parameters 𝐿, 𝑄 in arithmetic progressions, Math. Comp. 39 (1982), no. 159, 239–247. MR 658229, https://doi.org/10.1090/S0025-5718-1982-0658229-0
27. 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