International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Summation polynomials and the discrete logarithm problem on elliptic curves

Authors:
Igor Semaev
Download:
URL: http://eprint.iacr.org/2004/031
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12007,
  title={Summation polynomials and the discrete logarithm problem on elliptic curves},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / elliptic curves, summation polynomials, the discrete logarithm problem},
  url={http://eprint.iacr.org/2004/031},
  note={submitted to Crypto 2004 Igor.Semaev@wis.kuleuven.ac.be 12453 received 5 Feb 2004},
  author={Igor Semaev},
  year=2004
}