Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Fast primality tests for numbers less than $ 50\cdot 10\sp 9$


Authors: G. C. Kurtz, Daniel Shanks and H. C. Williams
Journal: Math. Comp. 46 (1986), 691-701
MSC: Primary 11Y11; Secondary 11A51, 11R16
DOI: https://doi.org/10.1090/S0025-5718-1986-0829639-7
MathSciNet review: 829639
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Consider the doubly infinite set of sequences $ A(n)$ given by

$\displaystyle A(n + 3) = rA(n + 2) - sA(n + 1) + A(n)$

with $ A( - 1) = s$, $ A(0) = 3$, $ A(1) = r$. For a given pair r,s, the "signature" of n is defined to be the sextet

$\displaystyle A( - n - 1),A( - n),A( - n + 1),A(n - 1),A(n),A(n + 1),$

each reduced modulo n. Primes have only three types of signatures, depending on how they split in the cubic field generated by $ {x^3} - r{x^2} + sx - 1$. 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 $ \leqslant 50 \cdot {10^9}$ in the Perrin sequence $ (r = 0,s = - 1)$. Also, some numbers which are acceptable composites for both the Perrin sequence and the sequence with $ r = 1$, $ s = 0$ are presented.

References [Enhancements On Off] (What's this?)

  • [1] W. Adams & D. Shanks, "Strong primality tests that are not sufficient," Math. Comp., v. 35, 1982, pp. 225-300. MR 658231 (84c:10007)
  • [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] C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to 25,000,000,000," Math. Comp., v. 35, 1980, pp. 1003-1026. MR 572872 (82g:10030)
  • [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] 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: https://doi.org/10.1090/S0025-5718-1986-0829639-7
Article copyright: © Copyright 1986 American Mathematical Society

American Mathematical Society