Strong primality tests that are not sufficient
Authors:
William Adams and Daniel Shanks
Journal:
Math. Comp. 39 (1982), 255300
MSC:
Primary 10A25; Secondary 1004, 1204
MathSciNet review:
658231
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A detailed investigation is given of the possible use of cubic recurrences in primality tests. No attempt is made in this abstract to cover all of the many topics examined in the paper. Define a doubly infinite set of sequences by with , , and . If n is prime, . Perrin asked if any composite satisfies this congruence if , . The answer is yes, and our first example leads us to strengthen the condition by introducing the "signature" of n: . Primes have three types of signatures depending on how they split in the cubic field generated by . Composites with "acceptable" signatures do exist but are very rare. The Stype signature, which corresponds to the completely split primes, has a very special role, and it may even be that I and Q type composites do not occur in Perrin's sequence even though the I and Q primes comprise ths of all primes. is easily computable in operations. The paper closes with a padic analysis. This powerful tool sets the stage for our [12] which will be Part II of the paper.
 [1]
R. Perrin, "Item 1484," L'Intermédiare des Math., v. 6, 1899, pp. 7677.
 [2]
E. Malo, ibid., v. 7, 1900, p. 281, p. 312.
 [2a]
E. B. Escott, ibid., v. 8, 1901, pp. 6364.
 [3]
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966.
 [4]
Daniel
Shanks, Calculation and applications of
Epstein zeta functions, Math. Comp. 29 (1975), 271–287.
Collection of articles dedicated to Derrick Henry Lehmer on the occasion of
his seventieth birthday. MR 0409357
(53 #13114a), http://dx.doi.org/10.1090/S00255718197504093572
 [5]
Daniel
Shanks, Five numbertheoretic algorithms, Proceedings of the
Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba,
Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973,
pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
(51 #8072)
 [6]
Donald Ervin Knuth, Seminumerical Algorithms, Second printing, AddisonWesley, Reading, Mass., 1971, esp. pp. 260266.
 [7]
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
 [8]
Daniel Shanks, "Review of Fröberg," ibid., v. 29, 1975, pp. 331333.
 [9]
Daniel
Shanks, A survey of quadratic, cubic and quartic algebraic number
fields (from a computational point of view), Proceedings of the
Seventh Southeastern Conference on Combinatorics, Graph Theory, and
Computing (Louisiana State Univ., Baton Rouge, La., 1976), Utilitas Math.,
Winnipeg, Man., 1976, pp. 15–40. Congressus Numerantium, No.
XVII. MR
0453691 (56 #11951)
 [10]
Daniel
Shanks, Class number, a theory of factorization, and genera,
1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State
Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence,
R.I., 1971, pp. 415–440. MR 0316385
(47 #4932)
 [11]
Daniel
Shanks, Solved and unsolved problems in number theory, 2nd
ed., Chelsea Publishing Co., New York, 1978. MR 516658
(80e:10003)
 [12]
William
G. Spohn Jr., Letter to the editor: “Incredible
identities” (Fibonacci Quart. 12 (1974), 271, 280) by Daniel
Shanks, Fibonacci Quart. 14 (1976), no. 1, 12.
MR
0384744 (52 #5617)
 [1]
 R. Perrin, "Item 1484," L'Intermédiare des Math., v. 6, 1899, pp. 7677.
 [2]
 E. Malo, ibid., v. 7, 1900, p. 281, p. 312.
 [2a]
 E. B. Escott, ibid., v. 8, 1901, pp. 6364.
 [3]
 Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966.
 [4]
 Daniel Shanks, "Calculation and applications of Epstein zeta functions," Math. Comp., v. 29, 1975, pp. 271287, esp. §8. MR 0409357 (53:13114a)
 [5]
 Daniel Shanks, "Five numbertheoretic algorithms," Proc. Second Manitoba Conf. on Numer. Math., 1972, pp. 5170, esp. §§5 and 6. MR 0371855 (51:8072)
 [6]
 Donald Ervin Knuth, Seminumerical Algorithms, Second printing, AddisonWesley, Reading, Mass., 1971, esp. pp. 260266.
 [7]
 C. Pomerance, J. L. Selfridge & S. S. Wagstaff, Jr., "The pseudoprimes to ," Math. Comp., v. 35, 1980, pp. 10031026. MR 572872 (82g:10030)
 [8]
 Daniel Shanks, "Review of Fröberg," ibid., v. 29, 1975, pp. 331333.
 [9]
 Daniel Shanks, "A survey of quadratic, cubic and quartic algebraic number fields (from a computational point of view)," Proc. 7th SE Conf. on Combinatorics, Graph Theory, and Computing, 1976, pp. 1540, esp. p. 32 and [36], [45], [47], [48] cited there. MR 0453691 (56:11951)
 [10]
 Daniel Shanks, "Class number, A theory of factorization, and genera," Proc. Sympos. Pure Math., Vol. 20, 1971, pp. 415440, esp. App. 1. MR 0316385 (47:4932)
 [11]
 Daniel Shanks, Solved and Unsolved Problems in Number Theory, Chelsea, New York, 1978, esp. Sec. 69. MR 516658 (80e:10003)
 [12]
 William Adams & Daniel Shanks, "Strong primality tests. IIAlgebraic identification of the padic limits and their implications." (To appear.) MR 0384744 (52:5617)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
10A25,
1004,
1204
Retrieve articles in all journals
with MSC:
10A25,
1004,
1204
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198206582319
PII:
S 00255718(1982)06582319
Article copyright:
© Copyright 1982
American Mathematical Society
