Paper 2004/153

A double large prime variation for small genus hyperelliptic index calculus

P. Gaudry, E. Thomë, N. Thëriault, and C. Diem

Abstract

In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.

Note: The paper now contains a complete proof of our result without any assumption or heuristic. Claus Diem is added as a co-author.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
discrete logarithm problemhyperelliptic curvesindex calculus
Contact author(s)
gaudry @ lix polytechnique fr
History
2005-11-21: last of 2 revisions
2004-07-07: received
See all versions
Short URL
https://ia.cr/2004/153
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/153,
      author = {P.  Gaudry and E.  Thomë and N.  Thëriault and C.  Diem},
      title = {A double large prime variation for small genus hyperelliptic index calculus},
      howpublished = {Cryptology ePrint Archive, Paper 2004/153},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/153}},
      url = {https://eprint.iacr.org/2004/153}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.