Paper 2004/031 Original: eprint.iacr.org/2004/031 ↗
Summation polynomials and the discrete logarithm problem on elliptic curves
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2004-02-05: last updated
- 2004-02-05: published
- Short URL
- https://ia.cr/2004/031
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2004/031,
author = {Igor Semaev},
title = {Summation polynomials and the discrete logarithm problem on elliptic curves},
howpublished = {Cryptology {ePrint} Archive, Paper 2004/031},
year = {2004},
url = {https://eprint.iacr.org/2004/031}
}