Mathematics of Computation

Author(s): Günter Löh; Wolfgang Niebuhr.
Journal: Math. Comp. 65 (1996), 823-836.
MSC (1991): Primary 11Y16; Secondary 11Y11, 11A51, 11--04
Retrieve article in: PDF
This article is available free of charge

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.

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 for which $a^{n-1}\equiv 1\pmod n$ for every prime to , 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 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 jusqu'à , 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).

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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS