Published online by Cambridge University Press: 18 May 2009
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).