Mathematics of Computation

Author(s): Jon Grantham.
Journal: Math. Comp. 70 (2001), 873-891.
MSC (2000): Primary 11Y11
Posted: March 1, 2000
Retrieve article in: PDF
This article is available free of charge

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.: 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 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 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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS