Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Higher-order Carmichael numbers


Author: Everett W. Howe
Journal: Math. Comp. 69 (2000), 1711-1719
MSC (1991): Primary 11A51; Secondary 11N25, 11Y11, 13B40
DOI: https://doi.org/10.1090/S0025-5718-00-01225-4
Published electronically: February 17, 2000
MathSciNet review: 1709151
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract:

We define a Carmichael number of order $m$ to be a composite integer $n$such that $n$th-power raising defines an endomorphism of every ${\mathbf Z}/n{\mathbf Z}$-algebra that can be generated as a ${\mathbf Z}/n{\mathbf Z}$-module by $m$elements. We give a simple criterion to determine whether a number is a Carmichael number of order $m$, and we give a heuristic argument (based on an argument of Erdos for the usual Carmichael numbers) that indicates that for every $m$ there should be infinitely many Carmichael numbers of order $m$. The argument suggests a method for finding examples of higher-order Carmichael numbers; we use the method to provide examples of Carmichael numbers of order $2$.


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

  • 1. W. W. ADAMS: Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), 1-15. MR 87k:11014
  • 2. W. W. ADAMS AND D. SHANKS: Strong primality tests that are not sufficient, Math. Comp. 39 (1982), 255-300. MR 84c:10007
  • 3. W. R. ALFORD, A. GRANVILLE, AND C. POMERANCE: There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), 703-722. MR 95k:11114
  • 4. R. BAILLIE AND S. S. WAGSTAFF, JR.: Lucas pseudoprimes, Math. Comp. 35 (1980), 1391-1417. MR 81j:10005
  • 5. A. DI PORTO AND P. FILIPPONI: Generating $M$-strong Fibonacci pseudoprimes, Fibonacci Quart. 30 (1992), 339-343. MR 93i:11013
  • 6. A. DI PORTO, P. FILIPPONI, AND E. MONTOLIVO: On the generalized Fibonacci pseudoprimes, Fibonacci Quart. 28 (1990), 347-354. MR 91m:11007
  • 7. P. ERDSOS: On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. MR 18:18e
  • 8. J. GRANTHAM: Frobenius pseudoprimes, Math. Comp. (to appear).
  • 9. S. GURAK: Cubic and biquadratic pseudoprimes of Lucas type, pp. 330-347 in Théorie des nombres (Quebec, PQ, 1987) (J.-M. De Koninck and C. Levesque, eds.), de Gruyter, Berlin-New York, 1989. MR 90k:11166
  • 10. C.-N. HSU: On Carmichael polynomials, J. Number Theory 71 (1998), 257-274. MR 99i:11116
  • 11. I. J: On generalized Lucas pseudoprimes, Acta. Math. Hungar. 55 (1990), 279-284. MR 92f:11004
  • 12. A. KORSELT: Problème chinois, L'Intermédiaire des Mathématiciens 6 (1899), 142-143.
  • 13. G. KOWOL: On strong Dickson pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 3 (1992), 129-138. MR 96g:11005
  • 14. J. S. MILNE: Étale Cohomology, Princeton University Press, Princeton, NJ, 1980. MR 81j:14002
  • 15. R. LIDL AND W. B. M¨ULLER: A note on strong Fibonacci pseudoprimes, pp. 311-317 in Advances in cryptology -- AUSCRYPT '90 (J. Seberry and J. Pieprzyk, eds.), Lecture notes in computer science 453, Springer, Berlin, 1990. MR 91k:11012
  • 16. R. LIDL AND W. B. M¨ULLER: Generalizations of the Fibonacci pseudoprimes test, Discrete Math. 92 (1991), 211-220. MR 93g:11010
  • 17. R. LIDL AND W. B. M¨ULLER: Primality testing with Lucas functions, Advances in cryptology -- AUSCRYPT '92 (J. Seberry and Y. Zheng, eds.), Lecture notes in computer science 718, Springer, Berlin, 1993. MR 95j:11121
  • 18. R. LIDL, W. B. M¨ULLER, AND A. OSWALD: Some remarks on strong Fibonacci pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 1 (1990), 59-65. MR 95k:11015
  • 19. F. MARKO: A note on pseudoprimes with respect to abelian linear recurring sequence, Math. Slovaca 46 (1996), 173-176. MR 97k:11009
  • 20. G. MARTIN: Lower bounds for the number of smooth values of a polynomial, electronic preprint available online at http://xxx.lanl.gov/abs/math.NT/9807102, 1998.
  • 21. S. M. S. M¨ULLER: Carmichael numbers and Lucas tests, pp. 193-202 in Finite Fields: Theory, Applications, and Algorithms (R. C. Mullin and G. L. Mullen, eds.), Contemp. Math. 225, American Mathematical Society, Providence, RI 1998. MR 99m:11008
  • 22. W. B. M¨ULLER AND A. OSWALD: Generalized Fibonacci pseudoprimes and probable primes, pp. 459-464 in Applications of Fibonacci numbers, Vol. 5 (G. E. Bergum, A. N. Philippou, and A. F. Horadam, eds.), Kluwer, Dordrecht, 1993. MR 95f:11105
  • 23. R. G. E. PINCH: The Carmichael numbers up to $10^{15}$, Math. Comp. 61 (1993), 381-391. MR 93m:11137
  • 24. R. G. E. PINCH: Compressed text file carmichael-16.gz, available by anonymous ftp at ftp://ftp.dpmms.cam.ac.uk/pub/rgep/Carmichael, 1992.
  • 25. C. POMERANCE: Are there counterexamples to the Baillie-PSW primality test?, Dopo le Parole (H. W. Lenstra, Jr., J. K. Lenstra, and P. Van Emde Boas, eds.), privately published, Amsterdam, 1984.
  • 26. G. SZEKERES: Higher order pseudoprimes in primality testing, pp. 451-458 in Combinatorics, Paul Erdos is eighty, Vol. 2 (Keszthely, 1993) (D. Miklós, V. T. Sós and T. Szonyi, eds.), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, 1996. MR 97c:11113
  • 27. H. C. WILLIAMS: On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), 133-143. MR 56:5414

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A51, 11N25, 11Y11, 13B40

Retrieve articles in all journals with MSC (1991): 11A51, 11N25, 11Y11, 13B40


Additional Information

Everett W. Howe
Affiliation: Center for Communications Research, 4320 Westerra Court, San Diego, CA 92121-1967, USA
Email: however@alumni.caltech.edu

DOI: https://doi.org/10.1090/S0025-5718-00-01225-4
Keywords: Carmichael number, pseudoprime, \'etale algebra
Received by editor(s): December 7, 1998
Published electronically: February 17, 2000
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society