Characterizing pseudoprimes for thirdorder linear recurrences
Author:
William W. Adams
Journal:
Math. Comp. 48 (1987), 115
MSC:
Primary 11A51; Secondary 1104, 11B37, 11Y11
MathSciNet review:
866094
Fulltext 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
(84c:10007), http://dx.doi.org/10.1090/S00255718198206582319
 [2]
Robert
Baillie and Samuel
S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518
(81j:10005), http://dx.doi.org/10.1090/S00255718198005835186
 [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
(87d:11101), http://dx.doi.org/10.1090/S00255718198608296397
 [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
(86g:11080)
 [5]
Gary
L. Miller, Riemann’s hypothesis and tests for primality,
J. Comput. System Sci. 13 (1976), no. 3,
300–317. Working papers presented at the ACMSIGACT Symposium on the
Theory of Computing (Albuquerque, N.M., 1975). MR 0480295
(58 #470a)
 [6]
Michael
O. Rabin, Probabilistic algorithm for testing primality, J.
Number Theory 12 (1980), no. 1, 128–138. MR 566880
(81f:10003), http://dx.doi.org/10.1016/0022314X(80)900840
 [7]
Kenneth
H. Rosen, Elementary number theory and its applications, 4th
ed., AddisonWesley, Reading, MA, 2000. MR 1739433
(2000i:11001)
 [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
0332640 (48 #10966)
 [9]
Daniel
Shanks, The simplest cubic fields, Math. Comp. 28 (1974), 1137–1152. MR 0352049
(50 #4537), http://dx.doi.org/10.1090/S00255718197403520498
 [10]
Daniel
Shanks, Solved and unsolved problems in number theory, 2nd
ed., Chelsea Publishing Co., New York, 1978. MR 516658
(80e:10003)
 [11]
D. Shanks & W. W. Adams, "Strong primality tests II. Algebraic identification of the Padic limits and their implications." (In preparation.)
 [12]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [1]
 W. W. Adams & D. Shanks, "Strong primality tests that are not sufficient," Math. Comp., v. 39, 1982, pp. 255300. MR 658231 (84c:10007)
 [2]
 R. Baillie & S. S. Wagstaff, "Lucas pseudoprimes," Math. Comp., v. 35, 1980, pp. 13911417. 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. 691701. 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. 123150. MR 697260 (86g:11080)
 [5]
 G. L. Miller, "Riemann's hypothesis and tests for primality," J. Comput. System Sci., v. 13, 1976, pp. 300317. MR 0480295 (58:470a)
 [6]
 M. O. Rabin, "Probabilistic algorithm for testing primality," J. Number Theory, v. 12, 1980, pp. 128138. MR 566880 (81f:10003)
 [7]
 K. Rosen, Elementary Number Theory and Its Applications, AddisonWesley, 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. 793797. MR 0332640 (48:10966)
 [9]
 D. Shanks, "The simplest cubic fields," Math. Comp., v. 28, 1974, pp. 11371152. 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 Padic limits and their implications." (In preparation.)
 [12]
 R. Solovay & V. Strassen, "A fast MonteCarlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485. MR 0429721 (55:2732)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11A51,
1104,
11B37,
11Y11
Retrieve articles in all journals
with MSC:
11A51,
1104,
11B37,
11Y11
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198708660946
PII:
S 00255718(1987)08660946
Article copyright:
© Copyright 1987
American Mathematical Society
