**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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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

**Short URL: **ia.cr/2004/031

[ Cryptology ePrint archive ]