### On the discrete logarithm problem for prime-field elliptic curves

Alessandro Amadori, Federico Pintore, and Massimiliano Sala

##### Abstract

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)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
elliptic curvediscrete logarithm problemprime fieldsummation polynomialsgroebner basis
Contact author(s)
federico pintore @ unitn it
History
Short URL
https://ia.cr/2017/609

CC BY

BibTeX

@misc{cryptoeprint:2017/609,
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{https://eprint.iacr.org/2017/609}},
url = {https://eprint.iacr.org/2017/609}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.