New primality criteria and factorizations of $2^{m}\pm 1$
HTML articles powered by AMS MathViewer
- by John Brillhart, D. H. Lehmer and J. L. Selfridge PDF
- Math. Comp. 29 (1975), 620-647 Request permission
Erratum: Math. Comp. 39 (1982), 747-757.
Erratum: Math. Comp. 39 (1982), 747.
Abstract:
A collection of theorems is developed for testing a given integer N for primality. The first type of theorem considered is based on the converse of Fermat’s theorem and uses factors of $N - 1$. The second type is based on divisibility properties of Lucas sequences and uses factors of $N + 1$. The third type uses factors of both $N - 1$ and $N + 1$ and provides a more effective, yet more complicated, primality test. The search bound for factors of $N \pm 1$ and properties of the hyperbola $N = {x^2} - {y^2}$ are utilized in the theory for the first time. A collection of 133 new complete factorizations of ${2^m} \pm 1$ and associated numbers is included, along with two status lists: one for the complete factorizations of ${2^m} \pm 1$; the other for the original Mersenne numbers.References
- M. BEELER, R. W. GOSPER & R. SCHROEPPEL, Artificial Intelligence Memo 239, MIT, Artificial Intelligence Laboratory, 1972, p. 13.
- John Brillhart, Concerning the numbers $2^{2p}+1$, $p$ prime, Math. Comp. 16 (1962), 424–430. MR 148593, DOI 10.1090/S0025-5718-1962-0148593-0 J. BRILLHART, "Some miscellaneous factorizations," Math. Comp., v. 17, 1963, pp. 447-450.
- John Brillhart and J. L. Selfridge, Some factorizations of $2^{n}\pm 1$ and related results, Math. Comp. 21 (1967), 87-96; corrigendum, ibid. 21 (1967), 751. MR 0224532, DOI 10.1090/S0025-5718-1967-0224532-3 M. KRAITCHIK, Théorie des Nombres, vol. 2, Gauthier-Villars, Paris, 1926, p. 135.
- D. H. Lehmer, Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc. 33 (1927), no. 3, 327–340. MR 1561374, DOI 10.1090/S0002-9904-1927-04368-3
- 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 E. LUCAS, "Considerations nouvelles sur la théorie des nombres premiers et sur la division géométrique de la circonference en parties égales," Assoc. Franç. Avancement Sci. C. R., v. 6, 1877, p. 162.
- Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques, Amer. J. Math. 1 (1878), no. 4, 289–321 (French). MR 1505176, DOI 10.2307/2369373
- Edouard Lucas, Théorie des nombres. Tome I: Le calcul des nombres entiers, le calcul des nombres rationnels, la divisibilité arithmétique, Librairie Scientifique et Technique Albert Blanchard, Paris, 1961 (French). Nouveau tirage augmenté dun avant-propos de Georges Bouligand. MR 0123503
- Michael A. Morrison, A note on primality testing using Lucas sequences, Math. Comp. 29 (1975), 181–182. MR 369234, DOI 10.1090/S0025-5718-1975-0369234-2
- Michael A. Morrison and John Brillhart, A method of factoring and the factorization of $F_{7}$, Math. Comp. 29 (1975), 183–205. MR 371800, DOI 10.1090/S0025-5718-1975-0371800-5 H. C. POCKLINGTON, "The determination of the prime or composite nature of large numbers by Fermat’s theorem," Proc. Cambridge Philos. Soc., v. 18, 1914-16, pp. 29-30. E. PROTH, "Théorèmes sur les nombres premiers," C.R. Acad. Sci. Paris, v. 87, 1878, p. 926.
- Hans Riesel, En bok om primtal, Studentlitteratur, Lund, 1968 (Swedish). MR 0269612
- 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
- Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703–710. MR 98057, DOI 10.2307/2309747
- Raphael M. Robinson, Some factorizations of numbers of the form $2^{n}\pm 1$, Math. Tables Aids Comput. 11 (1957), 265–268. MR 94313, DOI 10.1090/S0025-5718-1957-0094313-6
- J. L. Selfridge and Richard K. Guy, Primality testing with application to small machines, Proceedings of the Washington State University Conference on Number Theory (Washington State Univ., Pullman, Wash., 1971) Dept. Math., Washington State Univ., Pullman, Wash., 1971, pp. 45–51. MR 0319866
- H. C. Williams and C. R. Zarnke, A report on prime numbers of the forms $M=(6a+1)2^{2m-1}-1$ and $M^{\prime } =(6a-1)2^{2m}-1$, Math. Comp. 22 (1968), 420–422. MR 227095, DOI 10.1090/S0025-5718-1968-0227095-2
Additional Information
- © Copyright 1975 American Mathematical Society
- Journal: Math. Comp. 29 (1975), 620-647
- MSC: Primary 10A25
- DOI: https://doi.org/10.1090/S0025-5718-1975-0384673-1
- MathSciNet review: 0384673