Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T19:56:50.475Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  18 May 2009

S. Siksek  and
N. P. Smart
S. Siksek
Affiliation:
Institute of Mathematics and Statistics, University of Kent at Canterbury Canterbury, Kent CT2 7NF, England
N. P. Smart
Affiliation:
Hewlett-Packard Laboratories, Filton Road, Stoke Gifford, Bristol Bs12 6Qz, England
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

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).

Type
Research Article
Information
Glasgow Mathematical Journal , Volume 39 , Issue 3 , September 1997 , pp. 251 - 257
Copyright
Copyright © Glasgow Mathematical Journal Trust 1997

References

REFERENCES

1.Birch, B. J. and Swinnerton-Dyer, H. P. F., Notes on elliptic curves I, J. Reine Angew. Math. 212 (1963), 7–25.CrossRefGoogle Scholar
2.Brumer, A. and Kramer, K., The rank of elliptic curves, Duke Math. J., 44 (1977), 715–743.CrossRefGoogle 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.Google Scholar
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.Google Scholar
5.Cassels, J. W. S., Lectures on elliptic curves, LMS Student text 24 (1991).CrossRefGoogle Scholar
6.Cohen, H., A course in computational algebraic number theory (Springer-Verlag, 1993).CrossRefGoogle 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.Google Scholar
9.Merriman, J. R., Siksek, S. and Smart, N. P., Explicit 4-descents on an elliptic curve, Ada. Arith., 77 (1996), 385–404.CrossRefGoogle Scholar
10.Schaefer, E. F., 2-descent on the Jacobians of hyperelliptic curves, J. Number Theory, 51 (1995), 219–232.CrossRefGoogle Scholar
11.Silverman, J. H., The arithmetic of elliptic curves (Springer-Verlag, 1986).CrossRefGoogle Scholar
12.Thiel, C., Under the assumption of the Generalized Riemann Hypothesis verifying the class number belongs to , 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.CrossRefGoogle Scholar