Explicit primality criteria for $h\cdot 2^ k\pm 1$
HTML articles powered by AMS MathViewer
- by Wieb Bosma PDF
- Math. Comp. 61 (1993), 97-109 Request permission
Abstract:
Algorithms are described to obtain explicit primality criteria for integers of the form $h \cdot {2^k} \pm 1$ (in particular with h divisible by 3) that generalize classical tests for ${2^k} \pm 1$ in a well-defined finite sense. Numerical evidence (including all cases with $h < {10^5}$) seems to indicate that these finite generalizations exist for every h, unless $h = {4^m} - 1$ for some m, in which case it is proved they cannot exist.References
- Walter Borho, Große Primzahlen und befreundete Zahlen: Über den Lucas-Test und Thabit-Regeln, Mitt. Math. Ges. Hamburg 11 (1983), no. 2, 232–256 (German, with English summary). In collaboration with J. Buhl, H. Hoffmann, S. Mertens, E. Nebgen and R. Reckow. MR 744530 W. Bosma and M. P. M. van der Hulst, Primality proving with cyclotomy, Proefschrift (Ph.D. Thesis), Universiteit van Amsterdam, 1990.
- John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff Jr., Factorizations of $b^{n}\pm 1$, Contemporary Mathematics, vol. 22, American Mathematical Society, Providence, R.I., 1983. $b=2,\,3,\,5,\,6,\,7,\,10,\,11,\,12$ up to high powers. MR 715603
- John J. Cannon, An introduction to the group theory language, Cayley, Computational group theory (Durham, 1982) Academic Press, London, 1984, pp. 145–183. MR 760656
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- Richard K. Guy, Unsolved problems in number theory, Problem Books in Mathematics, Springer-Verlag, New York-Berlin, 1981. MR 656313 D. H. Lehmer, On Lucas’s test for the primality of Mersenne’s numbers, J. London Math. Soc. 10 (1935), 162-165.
- H. W. Lenstra Jr., Introduction, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 1–6. MR 700255
- Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques, Amer. J. Math. 1 (1878), no. 4, 289–321 (French). MR 1505176, DOI 10.2307/2369373
- 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
- Hans Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics, vol. 57, Birkhäuser Boston, Inc., Boston, MA, 1985. MR 897531, DOI 10.1007/978-1-4757-1089-2
- Raphael M. Robinson, A report on primes of the form $k\cdot 2^{n}+1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673–681. MR 96614, DOI 10.1090/S0002-9939-1958-0096614-7
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Math. Comp. 61 (1993), 97-109
- MSC: Primary 11A51; Secondary 11Y11
- DOI: https://doi.org/10.1090/S0025-5718-1993-1197510-3
- MathSciNet review: 1197510