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

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

MathSciNet review:
866094

Full-text PDF

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]**W. W. Adams & D. Shanks, "Strong primality tests that are not sufficient,"*Math. Comp.*, v. 39, 1982, pp. 255-300. MR**658231 (84c:10007)****[2]**R. Baillie & S. S. Wagstaff, "Lucas pseudoprimes,"*Math. Comp.*, v. 35, 1980, pp. 1391-1417. MR**583518 (81j:10005)****[3]**G. Kurtz, D. Shanks & H. C. Williams, "Fast primality tests for numbers less than ,"*Math. Comp.*, v. 46, 1986, pp. 691-701. MR**829639 (87d:11101)****[4]**H. W. Lenstra, "On the calculation of regulators and class numbers of quadratic fields,"*J. Arith.*, 1980 (J. V. Armitage, ed.), Cambridge Univ. Press, 1982, pp. 123-150. MR**697260 (86g:11080)****[5]**G. L. Miller, "Riemann's hypothesis and tests for primality,"*J. Comput. System Sci.*, v. 13, 1976, pp. 300-317. MR**0480295 (58:470a)****[6]**M. O. Rabin, "Probabilistic algorithm for testing primality,"*J. Number Theory*, v. 12, 1980, pp. 128-138. MR**566880 (81f:10003)****[7]**K. Rosen,*Elementary Number Theory and Its Applications*, Addison-Wesley, Reading, Mass., 1984. MR**1739433 (2000i:11001)****[8]**A. Rotkiewicz, "On the pseudoprimes with respect to the Lucas sequences,"*Bull. Acad. Polon. Sci.*, v. 21, 1973, pp. 793-797. MR**0332640 (48:10966)****[9]**D. Shanks, "The simplest cubic fields,"*Math. Comp.*, v. 28, 1974, pp. 1137-1152. MR**0352049 (50:4537)****[10]**D. Shanks,*Solved and Unsolved Problems in Number Theory*, Chelsea, New York, 1978. MR**516658 (80e:10003)****[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 & V. Strassen, "A fast Monte-Carlo test for primality,"*SIAM J. Comput.*, v. 6, 1977, pp. 84-85. MR**0429721 (55:2732)**

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:
https://doi.org/10.1090/S0025-5718-1987-0866094-6

Article copyright:
© Copyright 1987
American Mathematical Society