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
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).
(Received October 26 1995)