On the discrete logarithm problem in elliptic curves. II. (English) Zbl 1300.11132

Summary: We continue our study on the elliptic curve discrete logarithm problem over finite extension fields. We show, among others, the following results: For sequences of prime powers \((q_i)_{i\in\mathbb N}\) and natural numbers \((n_i)_{i\in\mathbb N}\) with \(n_i\to\infty\) and \(n_i/\log(q_i)^2\to 0\) for \(i\to\infty\), the discrete logarithm problem in the groups of rational points of elliptic curves over the fields \(\mathbb F_{q_i^{n_i}}\) can be solved in subexponential expected time \(\left(q_i^{n_i}\right)^{o(1)}\).
Let \(a, b>0\) be fixed. Then the problem over fields \(\mathbb F_{q^n}\), where \(q\) is a prime power and \(n\) a natural number with \(a\cdot\log(q)^{1/3}\leq n\leq b\cdot\log(q)\), can be solved in an expected time of \(e^{O\left(\log(q^n)^{3/4}\right)}\).
Part I, see Compos. Math. 147, No. 1, 75–104 (2011; Zbl 1213.11200).


11Y16 Number-theoretic algorithms; complexity
11G20 Curves over finite and local fields
14G15 Finite ground fields in algebraic geometry
14G50 Applications to coding theory and cryptography of arithmetic geometry
14H52 Elliptic curves


Zbl 1213.11200
Full Text: DOI