Glasgow Mathematical Journal

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)