Elliptic pseudoprimes

Authors:
I. Miyamoto and M. Ram Murty

Journal:
Math. Comp. **53** (1989), 415-430

MSC:
Primary 11G05; Secondary 11A51, 11Y11

DOI:
https://doi.org/10.1090/S0025-5718-1989-0970701-9

MathSciNet review:
970701

Full-text PDF

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 *n*th 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. London Math. Soc.*, v. 14, 1964, pp. 259-296. 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. 50-60.**[3]**P. Erdös, "On pseudoprimes and Carmichael numbers,"*Publ. Math. Debrecen*, v. 4, 1956, pp. 201-206. MR**0079031 (18:18e)****[4]**P. Erdös, "On the converse of Fermat's theorem,"*Amer. Math. Monthly*, v. 56, 1949, pp. 623-624. 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. 259-279. MR**815848 (87i:11183)****[6]**D. M. Gordon, "On the number of elliptic pseudoprimes,"*Math. Comp.*, v. 52, 1989, pp. 231-245. 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. 13-44. MR**834046 (87h:11050)****[9]**H. Halbertstam & H. E. Richert,*Sieve Methods*, Academic Press, London, 1974.**[10]**S. Lang,*Elliptic Functions*, Addison-Wesley, Reading, Mass., 1973. MR**0409362 (53:13117)****[11]**M. Ram Murty, "On Artin's conjecture,"*J. Number Theory*, v. 16, 1983, pp. 147-168.**[12]**Carl Pomerance, "On the distribution of pseudoprimes,"*Math. Comp.*, v. 37, 1981, pp. 587-593. MR**628717 (83k:10009)****[13]**J. H. Silverman,*The Arithmetic of Elliptic Curves*, Springer-Verlag, New York, 1986. MR**817210 (87g:11070)****[14]**J. T. Tate, "The arithmetic of elliptic curves,"*Invent. Math.*, v. 23, 1974, pp. 171-206. MR**0419359 (54:7380)**

Retrieve articles in *Mathematics of Computation*
with MSC:
11G05,
11A51,
11Y11

Retrieve articles in all journals with MSC: 11G05, 11A51, 11Y11

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1989-0970701-9

Article copyright:
© Copyright 1989
American Mathematical Society