Higher-order Carmichael numbers
HTML articles powered by AMS MathViewer
- by Everett W. Howe PDF
- Math. Comp. 69 (2000), 1711-1719 Request permission
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 Erdős 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
- William W. Adams, Characterizing pseudoprimes for third-order linear recurrences, Math. Comp. 48 (1987), no. 177, 1–15. MR 866094, DOI 10.1090/S0025-5718-1987-0866094-6
- William Adams and Daniel Shanks, Strong primality tests that are not sufficient, Math. Comp. 39 (1982), no. 159, 255–300. MR 658231, DOI 10.1090/S0025-5718-1982-0658231-9
- W. R. Alford, Andrew Granville, and Carl Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703–722. MR 1283874, DOI 10.2307/2118576
- Robert Baillie and Samuel S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518, DOI 10.1090/S0025-5718-1980-0583518-6
- Adina Di Porto and Piero Filipponi, Generating $M$-strong Fibonacci pseudoprimes, Fibonacci Quart. 30 (1992), no. 4, 339–343. MR 1188737
- Adina Di Porto, Piero Filipponi, and Emilio Montolivo, On the generalized Fibonacci pseudoprimes, Fibonacci Quart. 28 (1990), no. 4, 347–354. MR 1077501
- 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
- J. Grantham: Frobenius pseudoprimes, Math. Comp. (to appear).
- S. Gurak, Cubic and biquadratic pseudoprimes of Lucas type, Théorie des nombres (Quebec, PQ, 1987) de Gruyter, Berlin, 1989, pp. 330–347. MR 1024573
- Chih-Nung Hsu, On Carmichael polynomials, J. Number Theory 71 (1998), no. 2, 257–274. MR 1633817, DOI 10.1006/jnth.1998.2227
- I. Joó, On generalized Lucas pseudoprimes, Acta Math. Hungar. 55 (1990), no. 3-4, 279–284. MR 1091810, DOI 10.1007/BF01950936
- A. Korselt: Problème chinois, L’Intermédiaire des Mathématiciens 6 (1899), 142–143.
- G. Kowol, On strong Dickson pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 3 (1992), no. 2, 129–138. MR 1325751, DOI 10.1007/BF01387195
- James S. Milne, Étale cohomology, Princeton Mathematical Series, No. 33, Princeton University Press, Princeton, N.J., 1980. MR 559531
- Rudolf Lidl and Winfried B. Müller, A note on strong Fibonacci pseudoprimes, Advances in cryptology—AUSCRYPT ’90 (Sydney, 1990) Lecture Notes in Comput. Sci., vol. 453, Springer, Berlin, 1990, pp. 311–317. MR 1083782, DOI 10.1007/BFb0030371
- Rudolf Lidl and Winfried B. Müller, Generalizations of the Fibonacci pseudoprimes test, Discrete Math. 92 (1991), no. 1-3, 211–220. MR 1140588, DOI 10.1016/0012-365X(91)90282-7
- Rudolf Lidl and Winfried B. Müller, Primality testing with Lucas functions, Advances in cryptology—AUSCRYPT ’92 (Gold Coast, 1992) Lecture Notes in Comput. Sci., vol. 718, Springer, Berlin, 1993, pp. 539–542. MR 1292711, DOI 10.1007/3-540-57220-1_{9}2
- Rudolf Lidl, Winfried B. Müller, and Alan Oswald, Some remarks on strong Fibonacci pseudoprimes, Appl. Algebra Engrg. Comm. Comput. 1 (1990), no. 1, 59–65. MR 1325512, DOI 10.1007/BF01810848
- František Marko, A note on pseudoprimes with respect to abelian linear recurring sequence, Math. Slovaca 46 (1996), no. 2-3, 173–176. MR 1427002
- 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.
- Siguna M. S. Müller, Carmichael numbers and Lucas tests, Finite fields: theory, applications, and algorithms (Waterloo, ON, 1997) Contemp. Math., vol. 225, Amer. Math. Soc., Providence, RI, 1999, pp. 193–202. MR 1650628, DOI 10.1090/conm/225/03221
- Winfried B. Müller and Alan Oswald, Generalized Fibonacci pseudoprimes and probable primes, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992) Kluwer Acad. Publ., Dordrecht, 1993, pp. 459–464. MR 1271386
- 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
- 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.
- 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.
- G. Szekeres, Higher order pseudoprimes in primality testing, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993) Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 451–458. MR 1395869
- H. C. Williams, On numbers analogous to the Carmichael numbers, Canad. Math. Bull. 20 (1977), no. 1, 133–143. MR 447099, DOI 10.4153/CMB-1977-025-9
Additional Information
- Everett W. Howe
- Affiliation: Center for Communications Research, 4320 Westerra Court, San Diego, CA 92121-1967, USA
- MR Author ID: 236352
- ORCID: 0000-0003-4850-8391
- Email: however@alumni.caltech.edu
- Received by editor(s): December 7, 1998
- Published electronically: February 17, 2000
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1709151