Effective primality tests for some integers of the forms $A5^ n-1$ and $A7^ n-1$
HTML articles powered by AMS MathViewer
- by H. C. Williams PDF
- Math. Comp. 48 (1987), 385-403 Request permission
Abstract:
It is shown how polynomial time prime tests, which are both fast and deterministic, can be developed for many numbers of the form $A{r^n} - 1\;(r = 5,7;A < {r^n})$. 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 $2 \cdot {10^n} - 1$.References
-
C. Cailler, "Sur les congruences du troisième degrée," Enseign. Math., v. 10, 1908, pp. 474-487.
- L. Carlitz and H. H. Ferns, Some Fibonacci and Lucas identities, Fibonacci Quart. 8 (1970), no. 1, 61–73. MR 263733 L. E. Dickson, History of the Theory of Numbers, Vol. 1, Chelsea, New York, 1952.
- John H. Halton, On a general Fibonacci identity, Fibonacci Quart. 3 (1965), 31–43. MR 186613
- K. Inkeri, Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I No. 279 (1960), 19. MR 0117202
- Dov Jarden, Recurring sequences: A collection of papers, 2nd ed., Riveon Lematematika, Jerusalem (Israel), 1966. Revised and enlarged, including numerous new factorizations of Fibonacci and Lucas numbers by John Brillhart. MR 0197383
- D. H. Lehmer, An extended theory of Lucas’ functions, Ann. of Math. (2) 31 (1930), no. 3, 419–448. MR 1502953, DOI 10.2307/1968235
- D. H. Lehmer, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assoc. America, Buffalo, N.Y.; distributed by Prentice-Hall, Englewood Cliffs, N.J., 1969, pp. 117–151. MR 0246815
- 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, DOI 10.1145/320893.320906
- Hans Riesel, A note on the prime numbers of the forms $N=(6a+1)2^{2n-1}-1$ and $M=(6a-1)2^{2n}-1$, Ark. Mat. 3 (1956), 245–253. MR 76793, DOI 10.1007/BF02589411
- Hans Riesel, Lucasian criteria for the primality of $N=h\cdot 2^{n} -1$, Math. Comp. 23 (1969), 869–875. MR 262163, DOI 10.1090/S0025-5718-1969-0262163-1
- 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
- H. C. Williams, The primality of $N=2A3^{n}-1$, Canad. Math. Bull. 15 (1972), 585–589. MR 311559, DOI 10.4153/CMB-1972-101-7
- H. C. Williams, Some properties of a special set of recurring sequences, Pacific J. Math. 77 (1978), no. 1, 273–285. MR 507635, DOI 10.2140/pjm.1978.77.273
- H. C. Williams, The primality of certain integers of the form $2Ar^{n}-1$, Acta Arith. 39 (1981), no. 1, 7–17. MR 638738, DOI 10.4064/aa-39-1-7-17
- 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, DOI 10.2140/pjm.1982.98.477 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.
Additional Information
- © Copyright 1987 American Mathematical Society
- 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