Effective primality tests for some integers of the forms and

Author:
H. C. Williams

Journal:
Math. Comp. **48** (1987), 385-403

MSC:
Primary 11Y11; Secondary 11A51

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866123-X

MathSciNet review:
866123

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown how polynomial time prime tests, which are both fast and deterministic, can be developed for many numbers of the form . These tests, like the Lucas-Lehmer test for the primality of the Mersenne numbers, are derived by using the properties of the Lucas functions. We exemplify these ideas by using numbers of the form .

**[1]**C. Cailler, "Sur les congruences du troisième degrée,"*Enseign. Math.*, v. 10, 1908, pp. 474-487.**[2]**L. Carlitz and H. H. Ferns,*Some Fibonacci and Lucas identities*, Fibonacci Quart.**8**(1970), no. 1, 61–73. MR**263733****[3]**L. E. Dickson,*History of the Theory of Numbers*, Vol. 1, Chelsea, New York, 1952.**[4]**John H. Halton,*On a general Fibonacci identity*, Fibonacci Quart.**3**(1965), 31–43. MR**186613****[5]**K. Inkeri,*Tests for primality*, Ann. Acad. Sci. Fenn. Ser. A I No.**279**(1960), 19. MR**0117202****[6]**Dov Jarden,*Recurring sequences: A collection of papers*, Second edition. Revised and enlarged, including numerous new factorizations of Fibonacci and Lucas numbers by John Brillhart, Riveon Lematematika, Jerusalem (Israel), 1966. MR**0197383****[7]**D. H. Lehmer,*An extended theory of Lucas’ functions*, Ann. of Math. (2)**31**(1930), no. 3, 419–448. MR**1502953**, https://doi.org/10.2307/1968235**[8]**D. H. Lehmer,*Computer technology applied to the theory of numbers*, Studies in Number Theory, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N.J.), 1969, pp. 117–151. MR**0246815****[9]**Emma Lehmer and H. S. Vandiver,*On the computation of the number of solutions of certain trinomial congruences*, J. Assoc. Comput. Mach.**4**(1957), 505–510. MR**93908**, https://doi.org/10.1145/320893.320906**[10]**Hans Riesel,*A note on the prime numbers of the forms 𝑁=(6𝑎+1)2²ⁿ⁻¹-1 and 𝑀=(6𝑎-1)2²ⁿ-1*, Ark. Mat.**3**(1956), 245–253. MR**76793**, https://doi.org/10.1007/BF02589411**[11]**Hans Riesel,*Lucasian criteria for the primality of 𝑁=ℎ⋅2ⁿ-1*, Math. Comp.**23**(1969), 869–875. MR**262163**, https://doi.org/10.1090/S0025-5718-1969-0262163-1**[12]**H. C. Williams,*An algorithm for determining certain large primes*, Proceedings Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971) Louisiana State Univ., Baton Rouge, La., 1971, pp. 533–556. MR**0319874****[13]**H. C. Williams,*The primality of 𝑁=2𝐴3ⁿ-1*, Canad. Math. Bull.**15**(1972), 585–589. MR**311559**, https://doi.org/10.4153/CMB-1972-101-7**[14]**H. C. Williams,*Some properties of a special set of recurring sequences*, Pacific J. Math.**77**(1978), no. 1, 273–285. MR**507635****[15]**H. C. Williams,*The primality of certain integers of the form 2𝐴𝑟ⁿ-1*, Acta Arith.**39**(1981), no. 1, 7–17. MR**638738**, https://doi.org/10.4064/aa-39-1-7-17**[16]**H. C. Williams,*A class of primality tests for trinomials which includes the Lucas-Lehmer test*, Pacific J. Math.**98**(1982), no. 2, 477–494. MR**650024****[17]**C. R. Zarnke & H. C. Williams, "Computer determination of some large primes,"*Congressus Numerantium*III,*Proc. Second Louisiana Conf. on Combinatorics, Graph Theory and Computing*, Utilitas Math., Winnipeg, 1971, pp. 563-570.

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y11,
11A51

Retrieve articles in all journals with MSC: 11Y11, 11A51

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866123-X

Article copyright:
© Copyright 1987
American Mathematical Society