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

Diem, Claus

Algebra Number Theory 7, No. 6, 1281-1323 (2013).

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).

MSC:

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

Keywords:

elliptic curves; discrete logarithm problem

Citations:

Zbl 1213.11200