Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Explicit primality criteria for $ h\cdot 2\sp k\pm 1$


Author: Wieb Bosma
Journal: Math. Comp. 61 (1993), 97-109, S7
MSC: Primary 11A51; Secondary 11Y11
DOI: https://doi.org/10.1090/S0025-5718-1993-1197510-3
MathSciNet review: 1197510
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] W. Borho, Grosse Primzahlen und befreundete Zahlen: über den Lucas-test und Thabit Regeln, Mitt. Math. Ges. Hamburg (1983), 232-256. MR 744530 (85f:11094)
  • [2] W. Bosma and M. P. M. van der Hulst, Primality proving with cyclotomy, Proefschrift (Ph.D. Thesis), Universiteit van Amsterdam, 1990.
  • [3] J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $ {b^n} \pm 1,\;b = 2,3,5,6,7,10,11,12$ up to high powers, Contemp. Math., vol. 22, Amer. Math. Soc., Providence, RI, 1983. MR 715603 (84k:10005)
  • [4] J. J. Cannon, An introduction to the group theory language Cayley, Computational Group Theory (M. D. Atkinson, ed.) (Proceedings of the London Math. Soc. Symposium, Durham, July 30-August 9, 1982), Academic Press, London, 1984, pp. 143-182. MR 760656
  • [5] H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer, Berlin, 1993. MR 1228206 (94i:11105)
  • [6] R. K. Guy, Unsolved problems in number theory, Unsolved Problems in Intuitive Mathematics, vol. 1, Springer, Berlin, 1981. MR 656313 (83k:10002)
  • [7] D. H. Lehmer, On Lucas's test for the primality of Mersenne's numbers, J. London Math. Soc. 10 (1935), 162-165.
  • [8] H. W. Lenstra, Jr., Introduction, Computational Methods in Number Theory I (H. W. Lenstra, Jr., and R. Tijdeman, eds.), M. C. Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982, pp. 1-6. MR 700255 (85a:11007)
  • [9] E. Lucas, Théorie des fonctions numériques simplement périodiques. I, II, Amer. J. Math. 1 (1878), 184-239, 289-321. MR 1505176
  • [10] H. Riesel, Lucasian criteria for the primality of $ N = h \cdot {2^n} - 1$, Math. Comp. 23 (1969), 869-875. MR 0262163 (41:6773)
  • [11] -, Prime numbers and computer methods for factorization, Progr. Math., vol. 57, Birkhäuser, Boston, 1985, pp. 132-136. MR 897531 (88k:11002)
  • [12] R. M. Robinson, A report on primes of the form $ k{2^n} + 1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673-681. MR 0096614 (20:3097)

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1993-1197510-3
Article copyright: © Copyright 1993 American Mathematical Society

American Mathematical Society