A new algorithm for constructing large Carmichael numbers

Löh, Günter; Niebuhr, Wolfgang

doi:10.1090/S0025-5718-96-00692-8

A new algorithm for constructing large Carmichael numbers
HTML articles powered by AMS MathViewer

by Günter Löh and Wolfgang Niebuhr PDF

Math. Comp. 65 (1996), 823-836 Request permission

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

W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), 703–722.
Charles Hopkins, Rings with minimal condition for left ideals, Ann. of Math. (2) 40 (1939), 712–730. MR 12, DOI 10.2307/1968951
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232–238.
—, On composite numbers $P$ which satisfy the Fermat congruence $a^{P-1} \equiv 1 \pmod {P}$, Amer. Math. Monthly 19 (1912), 22–27.
J. Chernick, On Fermat’s simple theorem, Bull. Amer. Math. Soc. 45 (1939), 269–274.
H. Dubner, A new method for producing large Carmichael numbers, Math. Comp. 53 (1989), no. 187, 411–414. MR 969484, DOI 10.1090/S0025-5718-1989-0969484-8
Cahit Arf, Untersuchungen über reinverzweigte Erweiterungen diskret bewerteter perfekter Körper, J. Reine Angew. Math. 181 (1939), 1–44 (German). MR 18, DOI 10.1515/crll.1940.181.1
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989. A foundation for computer science. MR 1001562
D. Guillaume and F. Morain, Building Carmichael numbers with a large number of prime factors and generalization to other numbers, preprint, June 1992.
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
J. R. Hill, Large Carmichael numbers with three prime factors, Notices Amer. Math. Soc. 26 (1979), #79T–A–136.
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
G. Löh, Carmichael numbers with a large number of prime factors, Abstracts Amer. Math. Soc. 9 (1988), 329.
Günter Löh, Long chains of nearly doubled primes, Math. Comp. 53 (1989), no. 188, 751–759. MR 979939, DOI 10.1090/S0025-5718-1989-0979939-8
G. Löh and W. Niebuhr, Carmichael numbers with a large number of prime factors, II, Abstracts Amer. Math. Soc. 10 (1989), 305.
R. G. E. Pinch, The Carmichael numbers up to $10^{15}$, Math. Comp. 61 (1993), no. 203, 381–391. MR 1202611, DOI 10.1090/S0025-5718-1993-1202611-7
—, Some primality testing algorithms, Notices Amer. Math. Soc. 40 (1993), 1203–1210.
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.
P. A. Pritchard, A. Moran, and A. Thyssen, Twenty-two primes in arithmetic progression, Math. Comp. 64 (1995), 1337–1339.
S. Ramanujan, Highly composite numbers, Proc. London Math. Soc. (2) 14 (1915), 347–409.
Edward M. Reingold, Jurg Nievergelt, and Narsingh Deo, Combinatorial algorithms: theory and practice, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1977. MR 0471431
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
Samuel S. Wagstaff Jr., Large Carmichael numbers, Math. J. Okayama Univ. 22 (1980), no. 1, 33–41. MR 573668
Dale Woods and Joel Huenemann, Larger Carmichael numbers, Comput. Math. Appl. 8 (1982), no. 3, 215–216. MR 662584, DOI 10.1016/0898-1221(82)90044-X
Masataka Yorinaga, Numerical computation of Carmichael numbers, Math. J. Okayama Univ. 20 (1978), no. 2, 151–163. MR 519562
Masataka Yorinaga, Carmichael numbers with many prime factors, Math. J. Okayama Univ. 22 (1980), no. 2, 169–184. MR 595798
M. Zhang, Searching for large Carmichael numbers, Sichuan Daxue Xuebao 29 (1992), 472–474, (Chinese, abridged version in English).