Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Frobenius pseudoprimes

Author: Jon Grantham
Journal: Math. Comp. 70 (2001), 873-891
MSC (2000): Primary 11Y11
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.

References [Enhancements On Off] (What's this?)

  • 1. W. W. Adams, Characterizing pseudoprimes for third-order linear recurrence sequences, Math. Comp. 48 (1987), 1-15. MR 87k:11014
  • 2. W. W. Adams and D. Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300. MR 84c:10007
  • 3. W. R. Alford, Andrew Granville and Carl Pomerance, There are infinitely many Carmichael numbers, Annals of Mathematics 140 (1994), 703-722. MR 95k:11114
  • 4. W. R. Alford, Andrew Granville, and Carl Pomerance, On the difficulty of finding reliable witnesses, Algorithmic Number Theory (L. M. Adleman and M.-D. Huang, eds.), Lecture Notes in Comput. Sci., Springer-Verlag, New York, 1994, pp. 1-16. MR 96d:11136
  • 5. S. Arno, A note on Perrin pseudoprimes, Math. Comp. 56 (1991), 371-376. MR 91k:11011
  • 6. A. O. L. Atkin, Intelligent Primality Test Offer, Computational Perspectives on Number Theory (D. A. Buell and J. T. Teitelbaum, eds.), Proceedings of a Conference in Honor of A. O. L. Atkin, International Press, 1998, pp. 1-11. MR 98k:11183
  • 7. R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 81j:10005
  • 8. D. M. Gordon, Pseudoprimes on elliptic curves, Théorie des nombres (J. M. DeKoninck and C. Levesque, eds.), de Gruyter, Berlin, 1989, pp. 290-305. MR 91g:11158
  • 9. D. M. Gordon and C. Pomerance, The distribution of Lucas and elliptic pseudoprimes, Math. Comp. 57 (1991), 825-838; 60 (1993), 877. MR 92h:11081; MR 93h:11108
  • 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), 783-813. MR 91a:11067
  • 14. R. K. Guy, Unsolved Problems in Number Theory, Second Edition, Springer-Verlag, New York, 1994, p. 28. MR 96e:11002
  • 15. N. Jacobson, Basic Algebra I, Second Edition, W.H. Freeman, New York, 1985, p. 258. MR 86d:00001
  • 16. G. C. Kurtz, D. Shanks, and H. C. Williams, Fast primality tests for numbers less than $50\cdot 10\sp{9}$, Math. Comp. 46 (1986), 691-701. MR 87d:11101
  • 17. H. W. Lenstra, Jr., Primality testing, Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Part I, vol. 154, Math. Centre Tract, Amsterdam, 1982, pp. 55-77. MR 85g:11117
  • 18. Z. Mo and J. P. Jones, A new primality test using Lucas sequences, preprint.
  • 19. L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoretical Computer Science 12 (1980), 97-108. MR 82a:68078
  • 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. C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593. MR 83k:10009
  • 22. C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to $25\cdot 10^{9}$, Math. Comp. 35 (1980), 1003-1026. MR 82g:10030
  • 23. M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. MR 81f:10003
  • 24. R. M. Robinson, The converse of Fermat's theorem, Amer. Math. Monthly 64 (1957), 703-710. MR 20:4520
  • 25. 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. MR 46:8948
  • 26. A. Rotkiewicz, On Euler Lehmer pseudoprimes and Strong Lehmer pseudoprimes with parameters $L,Q$ in arithmetic progressions, Math. Comp. 39 (1982), 239-247. MR 83k:10004
  • 27. G. Szekeres, Higher order pseudoprimes in primality testing, Combinatorics, Paul Erdos is eighty, Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math Soc., Budapest, 1996, pp. 451-458. MR 97c:11113

Similar Articles

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

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

American Mathematical Society