Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A new algorithm
for constructing large Carmichael numbers


Authors: Günter Löh and Wolfgang Niebuhr
Journal: Math. Comp. 65 (1996), 823-836
MSC (1991): Primary 11Y16; Secondary 11Y11, 11A51, 11--04
DOI: https://doi.org/10.1090/S0025-5718-96-00692-8
MathSciNet review: 1325872
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe an algorithm for constructing Carmichael numbers $N$ with a large number of prime factors $p_{1}, p_{2}, \dots , p_{k}$. This algorithm starts with a given number $\Lambda =\operatorname {lcm} (p_{1}-1, p_{2}-1, \dots ,p_{k}-1)$, representing the value of the Carmichael function $\lambda (N)$. We found Carmichael numbers with up to $1101518$ factors.


References [Enhancements On Off] (What's this?)

  • 1. W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), 703--722. CMP 94:15
  • 2. N. G. W. H. Beeger, On composite numbers $n$ for which $a^{n-1}\equiv 1\pmod n$ for every $a$ prime to $n$, Scripta Math. 16 (1950), 133--135. MR 12:159e
  • 3. R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232--238.
  • 4. ------, On composite numbers $P$ which satisfy the Fermat congruence $a^{P-1} \equiv 1 \pmod {P}$, Amer. Math. Monthly 19 (1912), 22--27.
  • 5. J. Chernick, On Fermat's simple theorem, Bull. Amer. Math. Soc. 45 (1939), 269--274.
  • 6. H. Dubner, A new method for producing large Carmichael numbers, Math. Comp. 53 (1989), 411--414. MR 89m:11013
  • 7. P. Erd\H{o}s, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201--206. MR 18:18e
  • 8. R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete mathematics, Addison-Wesley, Reading, MA, 1989. MR 91f:00001
  • 9. D. Guillaume and F. Morain, Building Carmichael numbers with a large number of prime factors and generalization to other numbers, preprint, June 1992.
  • 10. G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., Clarendon Press, Oxford, 1979. MR 81i:10002
  • 11. J. R. Hill, Large Carmichael numbers with three prime factors, Notices Amer. Math. Soc. 26 (1979), #79T--A--136.
  • 12. D. E. Knuth, The art of computer programming, Vol. 2, 2nd ed., Addison-Wesley, Reading, MA, 1980. MR 83i:68003
  • 13. G. Löh, Carmichael numbers with a large number of prime factors, Abstracts Amer. Math. Soc. 9 (1988), 329.
  • 14. ------, Long chains of nearly doubled primes, Math. Comp. 53 (1989), 751--759. MR 90e:11015
  • 15. G. Löh and W. Niebuhr, Carmichael numbers with a large number of prime factors, II, Abstracts Amer. Math. Soc. 10 (1989), 305.
  • 16. R. G. E. Pinch, The Carmichael numbers up to $10^{15}$, Math. Comp. 61 (1993), 381--391. MR 93m:11137
  • 17. ------, Some primality testing algorithms, Notices Amer. Math. Soc. 40 (1993), 1203--1210.
  • 18. P. Poulet, Table des nombres composés vérifiant le théorème de Fermat pour le module $2$ jusqu'à $100.000.000$, Sphinx 8 (1938), 42--52; Corrections: MTE 485 , Math. Comp. 25 (1971), 944--945; MTE 497, Math. Comp. 26 (1972), 814.
  • 19. P. A. Pritchard, A. Moran, and A. Thyssen, Twenty-two primes in arithmetic progression, Math. Comp. 64 (1995), 1337--1339.
  • 20. S. Ramanujan, Highly composite numbers, Proc. London Math. Soc. (2) 14 (1915), 347--409.
  • 21. E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1977. MR 57:11164
  • 22. H. Riesel, Prime numbers and computer methods for factorization, Birkhäuser, Boston, MA, 1985. MR 88k:11002
  • 23. S. S. Wagstaff, Jr., Large Carmichael numbers, Math. J. Okayama Univ. 22 (1980), 33--41. MR 82c:10007
  • 24. D. Woods and J. Huenemann, Larger Carmichael numbers, Comput. Math. Appl. 8 (1982), 215--216. MR 83f:10017
  • 25. M. Yorinaga, Numerical computation of Carmichael numbers, Math. J. Okayama Univ. 20 (1978), 151--163. MR 80d:10026
  • 26. ------, Carmichael numbers with many prime factors, Math. J. Okayama Univ. 22 (1980), 169--184. MR 81m:10018
  • 27. M. Zhang, Searching for large Carmichael numbers, Sichuan Daxue Xuebao 29 (1992), 472--474, (Chinese, abridged version in English).

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16, 11Y11, 11A51, 11--04

Retrieve articles in all journals with MSC (1991): 11Y16, 11Y11, 11A51, 11--04


Additional Information

Günter Löh
Affiliation: Regionales Rechenzentrum der Universität Hamburg, Schlüterstraße 70, 20146 Hamburg, Germany
Email: rz2a011@rrz.uni-hamburg.de

Wolfgang Niebuhr
Affiliation: Regionales Rechenzentrum der Universität Hamburg, Schlüterstraße 70, 20146 Hamburg, Germany
Address at time of publication: Lisztstraße 6b, 22763 Hamburg, Germany
Email: 100117.256@compuserve.com

DOI: https://doi.org/10.1090/S0025-5718-96-00692-8
Keywords: Carmichael number, absolute pseudoprime, Carmichael function, algorithm
Received by editor(s): November 6, 1992
Received by editor(s) in revised form: October 11, 1994, and February 12, 1995
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society