Glasgow Mathematical Journal

Table of Contents - Volume 39 - Issue03

Research Article

On the complexity of computing the 2-Selmer group of an elliptic curve

S. Sikseka1 and N. P. Smarta2

a1 Institute of Mathematics and Statistics, University of Kent at Canterbury Canterbury, Kent CT2 7NF, England

a2 Hewlett-Packard Laboratories, Filton Road, Stoke Gifford, Bristol Bs12 6Qz, England

Abstract

In this paper we give an algorithm for computing the 2-Selmer group of an elliptic curve

S0017089500032183_eqnU1

which has complexity O(LD(0·5),c1)), where D is the absolute discriminant of the curve. Our algorithm is unconditional but the complexity estimate assumes the GRH and a standard conjecture on the distribution of smooth reduced ideals. This improves on the corresponding algorithm of Birch and Swinnerton-Dyer, which has complexity of O(√D).

(Received October 26 1995)

REFERENCES

  • 1. Birch, B. J. and Swinnerton-Dyer, H. P. F., Notes on elliptic curves I, J. Reine Angew. Math. 212 (1963), 7–25. [OpenURL Query Data]  [Google Scholar]
  • 2. Brumer, A. and Kramer, K., The rank of elliptic curves, Duke Math. J., 44 (1977), 715–743. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • 3. Buchmann, J., A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, in Séminaire de théorie des nombres, Paris (1988–1989), 28–41.
  • 4. Buchmann, J. and Lenstra, H. W. Jnr, Approximating rings of integers in number fields Journal de Theorie des Nombres de Bordeaux, 6 (1994), 221–260. [OpenURL Query Data]  [Google Scholar]
  • 5. Cassels, J. W. S., Lectures on elliptic curves, LMS Student text 24 (1991). [OpenURL Query Data]  [Google Scholar]
  • 6. Cohen, H., A course in computational algebraic number theory (Springer-Verlag, 1993). [Google Scholar]
  • 7. Cremona, J. E., Algorithms for modular elliptic curves (Cambridge University Press, 1992). [Google Scholar]
  • 8. Cremona, J. E., Classical invariants and 2-descent on elliptic curves, J. Symbolic Computation, 1997, to appear.
  • 9. Merriman, J. R., Siksek, S. and Smart, N. P., Explicit 4-descents on an elliptic curve, Ada. Arith., 77 (1996), 385–404. [OpenURL Query Data]  [Google Scholar]
  • 10. Schaefer, E. F., 2-descent on the Jacobians of hyperelliptic curves, J. Number Theory, 51 (1995), 219–232. [OpenURL Query Data]  [CrossRef]  [Google Scholar]
  • 11. Silverman, J. H., The arithmetic of elliptic curves (Springer-Verlag, 1986). [Google Scholar]
  • 12. Thiel, C., Under the assumption of the Generalized Riemann Hypothesis verifying the class number belongs to S0017089500032183_inline1, in ANTS-1: Algorithmic Number Theory, Eds Adelman, L. M. and Huang, M-D., Lecture Notes In Computer Science No. 877, (Springer-Verlag, 1994), 234–247. [Google Scholar]