Paper 2017/609

On the discrete logarithm problem for prime-field elliptic curves

Alessandro Amadori, Federico Pintore, and Massimiliano Sala


In recent years several papers have appeared investigating the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. However, with a notable exception by Petit et al. in 2016, all numerous papers have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach for the prime-field case. Our proposal outperforms both the original Semaev's method and Petit et al. specialized algorithm. The improvement is reached by reducing the necessary Groebner basis computations to only one basis calculation.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
elliptic curvediscrete logarithm problemprime fieldsummation polynomialsgroebner basis
Contact author(s)
federico pintore @ unitn it
2017-06-26: received
Short URL
Creative Commons Attribution


      author = {Alessandro Amadori and Federico Pintore and Massimiliano Sala},
      title = {On the discrete logarithm problem for prime-field elliptic curves},
      howpublished = {Cryptology ePrint Archive, Paper 2017/609},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.