|
Higher-order Carmichael numbers
Author:
Everett W. Howe
Journal:
Math. Comp. 69 (2000), 1711-1719
MSC (1991):
Primary 11A51; Secondary 11N25, 11Y11, 13B40
Posted:
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 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 .
- 1.
William
W. Adams, Characterizing pseudoprimes for
third-order linear recurrences, Math. Comp.
48 (1987), no. 177, 1–15. MR 866094
(87k:11014), http://dx.doi.org/10.1090/S0025-5718-1987-0866094-6
- 2.
William
Adams and Daniel
Shanks, Strong primality tests that are not
sufficient, Math. Comp. 39
(1982), no. 159, 255–300. MR 658231
(84c:10007), http://dx.doi.org/10.1090/S0025-5718-1982-0658231-9
- 3.
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
(95k:11114), http://dx.doi.org/10.2307/2118576
- 4.
Robert
Baillie and Samuel
S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), no. 152, 1391–1417. MR 583518
(81j:10005), http://dx.doi.org/10.1090/S0025-5718-1980-0583518-6
- 5.
Adina
Di Porto and Piero
Filipponi, Generating 𝑀-strong Fibonacci pseudoprimes,
Fibonacci Quart. 30 (1992), no. 4, 339–343. MR 1188737
(93i:11013)
- 6.
Adina
Di Porto, Piero
Filipponi, and Emilio
Montolivo, On the generalized Fibonacci pseudoprimes,
Fibonacci Quart. 28 (1990), no. 4, 347–354. MR 1077501
(91m:11007)
- 7.
P.
Erdös, On pseudoprimes and Carmichael numbers, Publ.
Math. Debrecen 4 (1956), 201–206. MR 0079031
(18,18e)
- 8.
J. GRANTHAM: Frobenius pseudoprimes, Math. Comp. (to appear).
- 9.
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
(90k:11166)
- 10.
Chih-Nung
Hsu, On Carmichael polynomials, J. Number Theory
71 (1998), no. 2, 257–274. MR 1633817
(99i:11116), http://dx.doi.org/10.1006/jnth.1998.2227
- 11.
I.
Joó, On generalized Lucas pseudoprimes, Acta Math.
Hungar. 55 (1990), no. 3-4, 279–284. MR 1091810
(92f:11004), http://dx.doi.org/10.1007/BF01950936
- 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), no. 2, 129–138. MR 1325751
(96g:11005), http://dx.doi.org/10.1007/BF01387195
- 14.
James
S. Milne, Étale cohomology, Princeton Mathematical
Series, vol. 33, Princeton University Press, Princeton, N.J., 1980. MR 559531
(81j:14002)
- 15.
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
(91k:11012), http://dx.doi.org/10.1007/BFb0030371
- 16.
Rudolf
Lidl and Winfried
B. Müller, Generalizations of the Fibonacci pseudoprimes
test, Discrete Math. 92 (1991), no. 1-3,
211–220. MR 1140588
(93g:11010), http://dx.doi.org/10.1016/0012-365X(91)90282-7
- 17.
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
(95j:11121), http://dx.doi.org/10.1007/3-540-57220-1_92
- 18.
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 (95k:11015), http://dx.doi.org/10.1007/BF01810848
- 19.
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
(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.
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
(99m:11008), http://dx.doi.org/10.1090/conm/225/03221
- 22.
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
(95f:11105)
- 23.
R.
G. E. Pinch, The Carmichael numbers up to
10¹⁵, Math. Comp.
61 (1993), no. 203, 381–391. MR 1202611
(93m:11137), http://dx.doi.org/10.1090/S0025-5718-1993-1202611-7
- 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,
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
(97c:11113)
- 27.
H.
C. Williams, On numbers analogous to the Carmichael numbers,
Canad. Math. Bull. 20 (1977), no. 1, 133–143.
MR
0447099 (56 #5414)
- 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 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:
http://dx.doi.org/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
Article copyright:
© Copyright 2000 American Mathematical Society
|