Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T23:22:53.406Z Has data issue: false hasContentIssue false
  • English
  • Français

On the discrete logarithm problem in elliptic curves

Part of: Arithmetic problems. Diophantine geometry Computational number theory

Published online by Cambridge University Press:  15 October 2010

Claus Diem
Claus Diem*
Affiliation:
University of Leipzig, Mathematical Institute, Johannisgasse 26, 04103 Leipzig, Germany (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

Keywords

elliptic curvesdiscrete logarithm problem

MSC classification

Secondary: 11Y16: Algorithms; complexity 14G15: Finite ground fields 14G50: Applications to coding theory and cryptography
Type
Research Article
Information
Compositio Mathematica , Volume 147 , Issue 1 , January 2011 , pp. 75 - 104
Copyright
Copyright © Foundation Compositio Mathematica 2010

References

[1]Bosch, S., Lütkebohmert, W. and Raynaud, W., Néron models (Springer, Berlin, 1980).Google Scholar
[2]Bosma, W., Cannon, J. and Playoust, C., The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), 235–265.CrossRefGoogle Scholar
[3]Canny, J., Generalized characteristic polynomials, J. Symbolic. Comput. 9 (1990), 241–250.CrossRefGoogle Scholar
[4]Diem, C., A study on theoretical and practical aspects of Weil-restrictions of varieties, PhD thesis, University of Essen (2001).Google Scholar
[5]Diem, C., On the discrete logarithm problem in class groups of curves. Math. Comp. (2009), doi: 10.1090/S0025-5718-2010-02281-1.CrossRefGoogle Scholar
[6]Fulton, W., Intersection theory (Springer, Berlin, 1984).CrossRefGoogle Scholar
[7]Fulton, W., Introduction to toric varieties (Princeton University Press, Princeton, NJ, 1993).CrossRefGoogle Scholar
[8]Gaudry, P., Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symbolic. Comput. 44 (2009), 1690–1702.CrossRefGoogle Scholar
[9]Gelfand, I., Kapranov, M. and Zelevinsky, A., Discriminants, resultants, and multidimensional determinants (Birkhäuser, Basel, 1994).CrossRefGoogle Scholar
[10]Grothendieck, A., Eléments de Géométrie Algébrique III, Première Partie, Publ. Math. 11 (1961).Google Scholar
[11]Hartshorne, R., Algebraic geometry (Springer, Berlin, 1977).CrossRefGoogle Scholar
[12]Kani, E. and Rosen, M., Idempotent relations and factors of Jacobians, Math. Ann. 284 (1989), 307–327.CrossRefGoogle Scholar
[13]Lenstra, H. W. and Pomerance, C., A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483–516.CrossRefGoogle Scholar
[14]Matsumura, H., Commutative ring theory (Cambridge University Press, Cambridge, 1989).Google Scholar
[15]Miller, V., The Weil pairing and its efficient computation, J. Cryptology 17 (2004), 235–261.CrossRefGoogle Scholar
[16]Rojas, J. M., Solving degenerate sparse polynomial systems faster, J. Symbolic. Comput. 28 (1999), 155–186.CrossRefGoogle Scholar
[17]Rosser, J. and Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.CrossRefGoogle Scholar
[18]Schoof, R., Elliptic curves over finite fields and the compuation of square roots mod p, Math. Comp. 44 (1985), 483–494.Google Scholar
[19]Semaev, I., Summation polynomials and the discrete logarithm problem on elliptic curves. Available under http://eprint.iacr.org/2004/031, 2004.Google Scholar
[20]Silverman, J., The arithmetic of elliptic curves (Springer, Berlin, 1986).CrossRefGoogle Scholar
[21]Stichtenoth, H., Algebraic function fields and codes (Springer, Berlin, 1993).Google Scholar