Elliptic pseudoprimes
Authors:
I. Miyamoto and M. Ram Murty
Journal:
Math. Comp. 53 (1989), 415430
MSC:
Primary 11G05; Secondary 11A51, 11Y11
MathSciNet review:
970701
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let E be an elliptic curve over Q with complex multiplication by an order in an imaginary quadratic field. Let denote the nth division polynomial, and let P be a rational point of E of infinite order. A natural number n is called an elliptic pseudoprime if and n is composite. Let denote the number of elliptic pseudoprimes up to x. We show that . More generally, if are r independent rational points of E which have infinite order, and is the subgroup generated by them, denote by the number of composite satisfying , . For , we prove for some positive constant c.
 [1]
J.
W. S. Cassels, Arithmetic on an elliptic curve, Proc.
Internat. Congr. Mathematicians (Stockholm, 1962) Inst. MittagLeffler,
Djursholm, 1963, pp. 234–246. MR 0175891
(31 #167)
 [2]
N. G. de Bruijn, "On the number of positive integers and free of prime factors ," Indag. Math., v. 13, 1951, pp. 5060.
 [3]
P.
Erdös, On pseudoprimes and Carmichael numbers, Publ.
Math. Debrecen 4 (1956), 201–206. MR 0079031
(18,18e)
 [4]
P.
Erdös, On the converse of Fermat’s theorem, Amer.
Math. Monthly 56 (1949), 623–624. MR 0032691
(11,331g)
 [5]
Paul
Erdős and Carl
Pomerance, On the number of false witnesses for a
composite number, Math. Comp.
46 (1986), no. 173, 259–279. MR 815848
(87i:11183), http://dx.doi.org/10.1090/S0025571819860815848X
 [6]
Daniel
M. Gordon, On the number of elliptic
pseudoprimes, Math. Comp.
52 (1989), no. 185, 231–245. MR 946604
(89f:11169), http://dx.doi.org/10.1090/S00255718198909466042
 [7]
D. M. Gordon, Private communication.
 [8]
Rajiv
Gupta and M.
Ram Murty, Primitive points on elliptic curves, Compositio
Math. 58 (1986), no. 1, 13–44. MR 834046
(87h:11050)
 [9]
H. Halbertstam & H. E. Richert, Sieve Methods, Academic Press, London, 1974.
 [10]
Serge
Lang, Elliptic functions, AddisonWesley Publishing Co., Inc.,
Reading, Mass.LondonAmsterdam, 1973. With an appendix by J. Tate. MR 0409362
(53 #13117)
 [11]
M. Ram Murty, "On Artin's conjecture," J. Number Theory, v. 16, 1983, pp. 147168.
 [12]
Carl
Pomerance, On the distribution of
pseudoprimes, Math. Comp.
37 (1981), no. 156, 587–593. MR 628717
(83k:10009), http://dx.doi.org/10.1090/S00255718198106287170
 [13]
Joseph
H. Silverman, The arithmetic of elliptic curves, Graduate
Texts in Mathematics, vol. 106, SpringerVerlag, New York, 1986. MR 817210
(87g:11070)
 [14]
John
T. Tate, The arithmetic of elliptic curves, Invent. Math.
23 (1974), 179–206. MR 0419359
(54 #7380)
 [1]
 J. W. S. Cassels, "Arithmetic on an elliptic curve," Proc. London Math. Soc., v. 14, 1964, pp. 259296. MR 0175891 (31:167)
 [2]
 N. G. de Bruijn, "On the number of positive integers and free of prime factors ," Indag. Math., v. 13, 1951, pp. 5060.
 [3]
 P. Erdös, "On pseudoprimes and Carmichael numbers," Publ. Math. Debrecen, v. 4, 1956, pp. 201206. MR 0079031 (18:18e)
 [4]
 P. Erdös, "On the converse of Fermat's theorem," Amer. Math. Monthly, v. 56, 1949, pp. 623624. MR 0032691 (11:331g)
 [5]
 P. Erdös & Carl Pomerance, "On the number of false witnesses for a composite number," Math. Comp., v. 46, 1986, pp. 259279. MR 815848 (87i:11183)
 [6]
 D. M. Gordon, "On the number of elliptic pseudoprimes," Math. Comp., v. 52, 1989, pp. 231245. MR 946604 (89f:11169)
 [7]
 D. M. Gordon, Private communication.
 [8]
 R. Gupta & M. Ram Murty, "Primitive points on elliptic curves," Compositio Math., v. 58, 1986, pp. 1344. MR 834046 (87h:11050)
 [9]
 H. Halbertstam & H. E. Richert, Sieve Methods, Academic Press, London, 1974.
 [10]
 S. Lang, Elliptic Functions, AddisonWesley, Reading, Mass., 1973. MR 0409362 (53:13117)
 [11]
 M. Ram Murty, "On Artin's conjecture," J. Number Theory, v. 16, 1983, pp. 147168.
 [12]
 Carl Pomerance, "On the distribution of pseudoprimes," Math. Comp., v. 37, 1981, pp. 587593. MR 628717 (83k:10009)
 [13]
 J. H. Silverman, The Arithmetic of Elliptic Curves, SpringerVerlag, New York, 1986. MR 817210 (87g:11070)
 [14]
 J. T. Tate, "The arithmetic of elliptic curves," Invent. Math., v. 23, 1974, pp. 171206. MR 0419359 (54:7380)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11G05,
11A51,
11Y11
Retrieve articles in all journals
with MSC:
11G05,
11A51,
11Y11
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198909707019
PII:
S 00255718(1989)09707019
Article copyright:
© Copyright 1989 American Mathematical Society
