Fast primality tests for numbers less than
Authors:
G. C. Kurtz, Daniel Shanks and H. C. Williams
Journal:
Math. Comp. 46 (1986), 691701
MSC:
Primary 11Y11; Secondary 11A51, 11R16
MathSciNet review:
829639
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Consider the doubly infinite set of sequences given by with , , . For a given pair r,s, the "signature" of n is defined to be the sextet each reduced modulo n. Primes have only three types of signatures, depending on how they split in the cubic field generated by . An "acceptable" composite is a composite integer which has the same type of signature as a prime; such integers are very rare. In this paper, a description is given of the results of a computer search for all acceptable composites in the Perrin sequence . Also, some numbers which are acceptable composites for both the Perrin sequence and the sequence with , are presented.
 [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]
R. Perrin, Item 1484, L'Intermédiaire des Math., v. 6, 1899, pp. 7677.
 [3]
E. Lucas, "Sur la recherche des grands nombres premiers," A. F. Congrès du ClermontFerrand, 1876, pp. 6168.
 [4]
Carl
Pomerance, J.
L. Selfridge, and Samuel
S. Wagstaff Jr., The pseudoprimes to
25⋅10⁹, Math. Comp.
35 (1980), no. 151, 1003–1026. MR 572872
(82g:10030), http://dx.doi.org/10.1090/S00255718198005728727
 [5]
D. Shanks, "Primesplitting in associated cubic and quartic fields: Some implications and some techniques." (To appear.)
 [6]
W. Adams & D. Shanks, "Strong primality tests. IIAlgebraic identification of the padic limits and their implications." (To appear.)
 [7]
William
W. Adams, Characterizing pseudoprimes for
thirdorder linear recurrences, Math. Comp.
48 (1987), no. 177, 1–15. MR 866094
(87k:11014), http://dx.doi.org/10.1090/S00255718198708660946
 [1]
 W. Adams & D. Shanks, "Strong primality tests that are not sufficient," Math. Comp., v. 35, 1982, pp. 225300. MR 658231 (84c:10007)
 [2]
 R. Perrin, Item 1484, L'Intermédiaire des Math., v. 6, 1899, pp. 7677.
 [3]
 E. Lucas, "Sur la recherche des grands nombres premiers," A. F. Congrès du ClermontFerrand, 1876, pp. 6168.
 [4]
 C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to 25,000,000,000," Math. Comp., v. 35, 1980, pp. 10031026. MR 572872 (82g:10030)
 [5]
 D. Shanks, "Primesplitting in associated cubic and quartic fields: Some implications and some techniques." (To appear.)
 [6]
 W. Adams & D. Shanks, "Strong primality tests. IIAlgebraic identification of the padic limits and their implications." (To appear.)
 [7]
 W. Adams, "Characterizing pseudoprimes for third order linear recurrences." (To appear.) MR 866094 (87k:11014)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y11,
11A51,
11R16
Retrieve articles in all journals
with MSC:
11Y11,
11A51,
11R16
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198608296397
PII:
S 00255718(1986)08296397
Article copyright:
© Copyright 1986
American Mathematical Society
