On the discrete logarithm problem in elliptic curves II

Diem, Claus

doi:10.2140/ant.2013.7.1281

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-7833 (online)

ISSN 1937-0652 (print)

Author index

To appear

Other MSP journals

On the discrete logarithm problem in elliptic curves II

Claus Diem

Vol. 7 (2013), No. 6, 1281–1323

DOI: 10.2140/ant.2013.7.1281

Abstract

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 ℕ}$ and natural numbers ${(n_{i})}_{i \in ℕ}$ 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 $F_{q_{i}^{n_{i}}}$ can be solved in subexponential expected time ${(q_{i}^{n_{i}})}^{o (1)}$ .

Let $a$ , $b > 0$ be fixed. Then the problem over fields $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 (log {(q^{n})}^{3 ∕ 4})}$ .

Keywords

elliptic curves, discrete logarithm problem

Mathematical Subject Classification 2010

Primary: 11Y16

Secondary: 14H52, 11G20

Milestones

Received: 28 July 2011

Revised: 12 June 2012

Accepted: 15 July 2012

Published: 19 September 2013

Authors

Claus Diem
Mathematical Institute University of Leipzig Augustusplatz 10 D-04109 Leipzig Germany

Vol. 7, No. 6, 2013