Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

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.

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

  • [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 $ 50 \cdot {10^9}$," 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)

Similar Articles

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

Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society