Elliptic pseudoprimes

Authors:
I. Miyamoto and M. Ram Murty

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

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

MathSciNet review:
970701

Full-text 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 *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. Internat. Congr. Mathematicians (Stockholm, 1962) Inst. Mittag-Leffler, Djursholm, 1963, pp. 234–246. MR**0175891****[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**4**(1956), 201–206. MR**0079031****[4]**P. Erdös,*On the converse of Fermat’s theorem*, Amer. Math. Monthly**56**(1949), 623–624. MR**0032691****[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**, 10.1090/S0025-5718-1986-0815848-X**[6]**Daniel M. Gordon,*On the number of elliptic pseudoprimes*, Math. Comp.**52**(1989), no. 185, 231–245. MR**946604**, 10.1090/S0025-5718-1989-0946604-2**[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****[9]**H. Halbertstam & H. E. Richert,*Sieve Methods*, Academic Press, London, 1974.**[10]**Serge Lang,*Elliptic functions*, Addison-Wesley Publishing Co., Inc., Reading, Mass.-London-Amsterdam, 1973. With an appendix by J. Tate. MR**0409362****[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.**37**(1981), no. 156, 587–593. MR**628717**, 10.1090/S0025-5718-1981-0628717-0**[13]**Joseph H. Silverman,*The arithmetic of elliptic curves*, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR**817210****[14]**John T. Tate,*The arithmetic of elliptic curves*, Invent. Math.**23**(1974), 179–206. MR**0419359**

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/S0025-5718-1989-0970701-9

Article copyright:
© Copyright 1989
American Mathematical Society