Cryptology ePrint Archive: Report 2004/031

Summation polynomials and the discrete logarithm problem on elliptic curves

Igor Semaev

Abstract: The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or low exponential time in the size of the input, one finds discrete logarithms faster than by means of Pollard's methods.

Category / Keywords: public-key cryptography / elliptic curves, summation polynomials, the discrete logarithm problem

Publication Info: submitted to Crypto 2004

Date: received 5 Feb 2004

Contact author: Igor Semaev at wis kuleuven ac be

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040205:222124 (All versions of this report)

Discussion forum: Show discussion | Start new discussion