Characterizing pseudoprimes for third-order linear recurrences

Author:
William W. Adams

Journal:
Math. Comp. **48** (1987), 1-15

MSC:
Primary 11A51; Secondary 11-04, 11B37, 11Y11

MathSciNet review:
866094

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper continues the work begun by D. Shanks and myself in [1] where certain cubic recurrences were used to give a very strong primality test. A complete characterization of the pseudoprimes for this test is given in terms of the periods of the corresponding sequences. Then these results are used to produce various types of pseudoprimes. A discussion of open problems is included.

**[1]**William Adams and Daniel Shanks,*Strong primality tests that are not sufficient*, Math. Comp.**39**(1982), no. 159, 255–300. MR**658231**, 10.1090/S0025-5718-1982-0658231-9**[2]**Robert Baillie and Samuel S. Wagstaff Jr.,*Lucas pseudoprimes*, Math. Comp.**35**(1980), no. 152, 1391–1417. MR**583518**, 10.1090/S0025-5718-1980-0583518-6**[3]**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**, 10.1090/S0025-5718-1986-0829639-7**[4]**H. W. Lenstra Jr.,*On the calculation of regulators and class numbers of quadratic fields*, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR**697260****[5]**Gary L. Miller,*Riemann’s hypothesis and tests for primality*, J. Comput. System Sci.**13**(1976), no. 3, 300–317. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N.M., 1975). MR**0480295****[6]**Michael O. Rabin,*Probabilistic algorithm for testing primality*, J. Number Theory**12**(1980), no. 1, 128–138. MR**566880**, 10.1016/0022-314X(80)90084-0**[7]**Kenneth H. Rosen,*Elementary number theory and its applications*, 4th ed., Addison-Wesley, Reading, MA, 2000. MR**1739433****[8]**A. Rotkiewicz,*On the pseudoprimes with respect to the Lucas sequences*, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.**21**(1973), 793–797 (English, with Russian summary). MR**0332640****[9]**Daniel Shanks,*The simplest cubic fields*, Math. Comp.**28**(1974), 1137–1152. MR**0352049**, 10.1090/S0025-5718-1974-0352049-8**[10]**Daniel Shanks,*Solved and unsolved problems in number theory*, 2nd ed., Chelsea Publishing Co., New York, 1978. MR**516658****[11]**D. Shanks & W. W. Adams, "Strong primality tests II. Algebraic identification of the*P*-adic limits and their implications." (In preparation.)**[12]**R. Solovay and V. Strassen,*A fast Monte-Carlo test for primality*, SIAM J. Comput.**6**(1977), no. 1, 84–85. MR**0429721**

Retrieve articles in *Mathematics of Computation*
with MSC:
11A51,
11-04,
11B37,
11Y11

Retrieve articles in all journals with MSC: 11A51, 11-04, 11B37, 11Y11

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1987-0866094-6

Article copyright:
© Copyright 1987
American Mathematical Society