zbMATH — the first resource for mathematics

On the complexity of computing the 2-Selmer group of an elliptic curve. (English) Zbl 0915.11032
Let \(E\) be an elliptic curve over \(\mathbb{Q}\) given by \[ E: Y^2= X^3+ AX+ B, \] and assume \(E\) has no points of order 2 defined over \(\mathbb{Q}\). The authors give an algorithm for computing the 2-Selmer group of \(E\) which in theory improves on the corresponding classical algorithm of B. J. Birch and H. P. F. Swinnerton-Dyer [J. Reine Angew. Math. 212, 7–25 (1963; Zbl 0118.27601)] in that its complexity of \[ O(\exp[(\log D\cdot\log\log D)^{{1\over 2}}(c_1+ o(1))]) \] is better than that of Birch and Swinnerton-Dyer (which is at least \(O(\sqrt D))\). Here, \(D\) denotes the absolute discriminant of the curve \(E\). However, as the authors admit, in practice the Birch and Swinnerton-Dyer algorithm will probably be much faster than their method, which is asymptotically faster as the former has seen many improvements over the years [e.g. see J. Cremona, J. Symb. Comput. 31, No. 1-2, 71–87 (2001; Zbl 0965.11025)].
The authors’ algorithm is unconditional, but is complexity estimate assumes the GRH and a standard conjecture on the distribution of smooth reduced ideals.

11G05 Elliptic curves over global fields
14Q05 Computational aspects of algebraic curves
14H52 Elliptic curves
Full Text: DOI
[1] Buchmann, Journal de Theorie des Nombres de Bordeaux 6 pp 221– (1994) · Zbl 0828.11075
[2] DOI: 10.1215/S0012-7094-77-04431-3 · Zbl 0376.14011
[3] Birch, J. Reine Angew. Math. 212 pp 7– (1963) · Zbl 0118.27601
[4] Thiel, Algorithmic Number Theory pp 234– (1994)
[5] Cassels, Lectures on elliptic curves 24 (1991)
[6] Merriman, Ada. Arith. 77 pp 385– (1996)
[7] DOI: 10.1006/jnth.1995.1044 · Zbl 0832.14016
[8] Cremona, Algorithms for modular elliptic curves (1992)
[9] Cohen, A course in computational algebraic number theory (1993) · Zbl 0786.11071
[10] Silverman, The arithmetic of elliptic curves (1986) · Zbl 0585.14026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.