Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ {\psi _n}$ 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 $ n\vert{\psi _{n + 1}}(P)$ and n is composite. Let $ N(x)$ denote the number of elliptic pseudoprimes up to x. We show that $ N(x) \ll x{(\log \log x)^{7/2}}/{(\log x)^{3/2}}$. More generally, if $ {P_1}, \ldots ,{P_r}$ are r independent rational points of E which have infinite order, and $ \Gamma $ is the subgroup generated by them, denote by $ {N_\Gamma }(x)$ the number of composite $ n \leq x$ satisfying $ n\vert{\psi _{n + 1}}({P_i})$, $ 1 \leq i \leq r$. For $ r \geq 2$, we prove $ {N_\Gamma }(x) \ll x\exp ( - c\sqrt {(\log x)(\log \log x))} $ for some positive constant c.


References [Enhancements On Off] (What's this?)

  • [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 $ \leq x$ and free of prime factors $ > y$," 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)

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: https://doi.org/10.1090/S0025-5718-1989-0970701-9
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society