Higher-order Carmichael numbers

Howe, Everett

doi:10.1090/S0025-5718-00-01225-4

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