|
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 to be a composite integer such that th-power raising defines an endomorphism of every -algebra that can be generated as a -module by elements. We give a simple criterion to determine whether a number is a Carmichael number of order , and we give a heuristic argument (based on an argument of Erdos for the usual Carmichael numbers) that indicates that for every there should be infinitely many Carmichael numbers of order . 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 .
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
-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. JOÓ: 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
, 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
|