Characterizing pseudoprimes for third-order linear recurrences

Adams, William W.

doi:10.1090/S0025-5718-1987-0866094-6

Characterizing pseudoprimes for third-order linear recurrences
HTML articles powered by AMS MathViewer

by William W. Adams PDF

Math. Comp. 48 (1987), 1-15 Request permission

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

William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255–300. MR 658231, DOI 10.1090/S0025-5718-1982-0658231-9
Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
G. C. Kurtz, Daniel Shanks, and H. C. Williams, Fast primality tests for numbers less than $50\cdot 10^9$, Math. Comp. 46 (1986), no. 174, 691–701. MR 829639, DOI 10.1090/S0025-5718-1986-0829639-7
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
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
Kenneth H. Rosen, Elementary number theory and its applications, 4th ed., Addison-Wesley, Reading, MA, 2000. MR 1739433
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 332640
Daniel Shanks, The simplest cubic fields, Math. Comp. 28 (1974), 1137–1152. MR 352049, DOI 10.1090/S0025-5718-1974-0352049-8
Daniel Shanks, Solved and unsolved problems in number theory, 2nd ed., Chelsea Publishing Co., New York, 1978. MR 516658

P

R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006