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