Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

The Carmichael numbers up to $ 10\sp {15}$


Author: R. G. E. Pinch
Journal: Math. Comp. 61 (1993), 381-391
MSC: Primary 11Y11; Secondary 11Y70
DOI: https://doi.org/10.1090/S0025-5718-1993-1202611-7
MathSciNet review: 1202611
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: There are 105212 Carmichael numbers up to $ {10^{15}}$: we describe the calculations. The numbers were generated by a back-tracking search for possible prime factorizations, and the computations checked by searching selected ranges of integers directly using a sieving technique, together with a "large-prime variation".


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. (to appear). MR 1283874 (95k:11114)
  • [2] N. G. W. H. Beeger, On composite numbers n for which $ {a^{n - 1}} \equiv 1 \bmod n$ for every a prime to n, Scripta Math. 16 (1950), 133-135. MR 0036773 (12:159e)
  • [3] R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1909-1910), 232-238. MR 1558896
  • [4] -, On composite numbers P which satisfy the congruence $ {a^{P - 1}} \equiv 1 \bmod P$, Amer. Math. Monthly 19 (1912), 22-27. MR 1517641
  • [5] I. Damgård and P. Landrock, Improved bounds for the Rabin primality test, preprint, 12 March 1992, Coding and Cryptography III, Proc. 3rd IMA Conf. on Coding and Cryptography (M. Ganley, ed.), Cirencester, December 1991 (to appear).
  • [6] I. Damgård, P. Landrock, and C. Pomerance, Average case error estimates for the strong probable prime test, Math. Comp. 61 (1993), 177-194. MR 1189518 (94b:11124)
  • [7] J. H. Davenport, Primality testing revisited, preprint, 20 April 1992, Proceedings ISSAC 1992 (P. S. Wang, ed.), ACM, New York, 1992.
  • [8] A. Di Porto and P. Filipponi, A probabilistic primality test based on the properties of certain generalized Lucas numbers, Advances in Cryptology--Eurocrypt' 88 (C. G. Günther, ed.), Lecture Notes in Comput. Sci., vol. 330, Springer-Verlag, Berlin and New York, 1988, pp. 211-223. MR 994664 (90f:11099)
  • [9] H. Duparc, On Carmichael numbers, Simon Stevin 29 (1951-1952), 21-24. MR 0048492 (14:21f)
  • [10] A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc. 39 (1992), 696-700.
  • [11] D. Guillaume, Table des nombres de Carmichael inférieurs à $ {10^{12}}$, preprint, May 1991.
  • [12] A. Guthmann, On the computation of Carmichael numbers, Universität Kaiserslautern, preprint 218, April 1992.
  • [13] G. Jaeschke, The Carmichael numbers to $ {10^{12}}$, Math. Comp. 55 (1990), 383-389. MR 1023763 (90m:11018)
  • [14] W. Keller, The Carmichael numbers to $ {10^{13}}$, Abstracts Amer. Math. Soc. 9 (1988), 328-329.
  • [15] W. Knödel, Carmichaelsche Zahlen, Math. Nachr. 9 (1953), 343-350. MR 0055360 (14:1062f)
  • [16] R. Lidl and W. B. Müller, A note on strong Fibonacci pseudoprimes, Advances in Cryptology--Auscrypt '90 (J. Seberry and J. Pieprzyk, eds.), Lecture Notes in Comput. Sci., vol. 453, Springer-Verlag, Berlin and New York, 1990, pp. 311-317. MR 1083782 (91k:11012)
  • [17] R. Lidl, W. B. Müller and A. Oswald, Some remarks on strong Fibonacci pseudoprimes, Applicable Algebra in Engineering, Communication and Computing 1 (1990), 59-65. MR 1325512 (95k:11015)
  • [18] F. J. McDonnell, Rabin's algorithm and the proportion of 'liars' for various families of numbers, University of Warwick, preprint, March 1989.
  • [19] W. B. Müller and A. Oswald, Dickson pseudoprimes and primality testing, Advances in cryptology--Eurocrypt '91 (D.W. Davies, ed.), Lecture Notes in Comput. Sci., vol. 547, Springer-Verlag, Berlin and New York, 1991, pp. 512-516. MR 1227820
  • [20] R. G. E. Pinch, The pseudoprimes up to $ {10^{12}}$, preprint, June, 1992.
  • [21] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593. MR 628717 (83k:10009)
  • [22] -, Two methods in elementary analytic number theory, Number Theory and Applications (R. A. Mollin, ed.), Kluwer, Dordrecht, 1989.
  • [23] C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $ {25.10^9}$, Math. Comp. 35 (1980), 1003-1026. MR 572872 (82g:10030)
  • [24] P. Ribenboim, The book of prime number records, Springer-Verlag, Berlin and New York, 1988. MR 931080 (89e:11052)
  • [25] -, The little book of big primes, Springer-Verlag, Berlin and New York, 1991. MR 1118843 (92i:11008)
  • [26] J. D. Swift, Review 13--Table of Carmichael numbers to $ {10^9}$, Math. Comp. 29 (1975), 338-339. MR 0655816 (58:31707)
  • [27] H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), 133-143. MR 0447099 (56:5414)
  • [28] M. Yorinaga, Numerical computation of Carmichael numbers, Math. J. Okayama Univ. 20 (1978), 151-163; II, 21 (1979), 183-205. MR 519562 (80d:10026)

Similar Articles

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

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


Additional Information

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

American Mathematical Society