Cryptology ePrint Archive: Report 2017/1262

A New Index Calculus Algorithm for the Elliptic Curve Discrete Logarithm Problem and Summation Polynomial Evaluation

Gary McGuire and Daniela Mueller

Abstract: The introduction of summation polynomials for elliptic curves by Semaev has opened up new avenues of investigation in index calculus type algorithms for the elliptic curve discrete logarithm problem, and several recent papers have explored their use. We propose an index calculus algorithm to solve the Elliptic Curve Discrete Logarithm Problem that makes use of a technique for fast evaluation of the summation polynomials, and unlike all other algorithms using summation polynomials, does not involve a Gr{\"o}bner basis computation. We further propose another algorithm that does not involve Gr{\"o}bner basis computations or summation polynomials. We give a complexity estimate of our algorithms and provide extensive computational data.

Category / Keywords: discrete logarithm problem, elliptic curve cryptosystem

Date: received 29 Dec 2017, last revised 8 Aug 2018

Contact author: gary mcguire at ucd ie

Available format(s): PDF | BibTeX Citation

Note: Presentation improved and Lemma 5.10 added.

Version: 20180808:105841 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]