On the discrete logarithm problem in elliptic curves
Claus Diem · Compositio Mathematica · 2010
Abstract We study the elliptic curve discrete logarithm problem over finite extension fields. We show that for any sequences of prime powers ( q i ) i ∈ℕ and natural numbers ( n i ) i ∈ℕ with n i ⟶ ∞ and n i /log ( q i )⟶0 for i ⟶ ∞ , the elliptic curve discrete logarithm problem restricted to curves over the fields 𝔽 q n i i can be solved in subexponential expected time ( q n i i ) o (1) . We also show that there exists a sequence of prime powers ( q i ) i ∈ℕ such that the problem restricted to curves over 𝔽 q i can be solved in an expected time of e 𝒪(log ( q i ) 2/3 ) .