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 D. Shanks & W. W. Adams, "Strong primality tests II. Algebraic identification of the P-adic limits and their implications." (In preparation.)
- 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
Additional Information
- © Copyright 1987 American Mathematical Society
- 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