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).
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
- Received by editor(s): November 6, 1992
- Received by editor(s) in revised form: October 11, 1994, and February 12, 1995
- © Copyright 1996 American Mathematical Society
- 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