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

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 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, https://doi.org/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, https://doi.org/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, https://doi.org/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. MR 480295, https://doi.org/10.1016/S0022-0000(76)80043-8
[6] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, https://doi.org/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 332640
[9] Daniel Shanks, The simplest cubic fields, Math. Comp. 28 (1974), 1137–1152. MR 352049, https://doi.org/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 429721, https://doi.org/10.1137/0206006