Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

Higher-order Carmichael numbers

Author(s): Everett W. Howe.
Journal: Math. Comp. 69 (2000), 1711-1719.
MSC (1991): Primary 11A51; Secondary 11N25, 11Y11, 13B40
Posted: February 17, 2000
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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:

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 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: 10.1090/S0025-5718-00-01225-4
PII: S 0025-5718(00)01225-4
Keywords: Carmichael number, pseudoprime, \'etale algebra
Received by editor(s): December 7, 1998
Posted: February 17, 2000
Copyright of article: Copyright 2000, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google