Fast primality tests for numbers less than

Authors:
G. C. Kurtz, Daniel Shanks and H. C. Williams

Journal:
Math. Comp. **46** (1986), 691-701

MSC:
Primary 11Y11; Secondary 11A51, 11R16

MathSciNet review:
829639

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Consider the doubly infinite set of sequences given by

*n*is defined to be the sextet

*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**, 10.1090/S0025-5718-1982-0658231-9**[2]**R. Perrin, Item 1484,*L'Intermédiaire des Math.*, v. 6, 1899, pp. 76-77.**[3]**E. Lucas, "Sur la recherche des grands nombres premiers," A. F.*Congrès du Clermont-Ferrand*, 1876, pp. 61-68.**[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**, 10.1090/S0025-5718-1980-0572872-7**[5]**D. Shanks, "Prime-splitting in associated cubic and quartic fields: Some implications and some techniques." (To appear.)**[6]**W. Adams & D. Shanks, "Strong primality tests. II-Algebraic identification of the*p*-adic limits and their implications." (To appear.)**[7]**William W. Adams,*Characterizing pseudoprimes for third-order linear recurrences*, Math. Comp.**48**(1987), no. 177, 1–15. MR**866094**, 10.1090/S0025-5718-1987-0866094-6

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/S0025-5718-1986-0829639-7

Article copyright:
© Copyright 1986
American Mathematical Society