International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A double large prime variation for small genus hyperelliptic index calculus

Authors:
P. Gaudry
Emmanuel Thomé
N. Thériault
C. Diem
Download:
URL: http://eprint.iacr.org/2004/153
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2004-12125,
  title={A double large prime variation for small genus hyperelliptic index calculus},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / discrete logarithm problem, hyperelliptic curves, index calculus},
  url={http://eprint.iacr.org/2004/153},
  note={ gaudry@lix.polytechnique.fr 13108 received 4 Jul 2004, last revised 21 Nov 2005},
  author={P. Gaudry and Emmanuel Thomé and N. Thériault and C. Diem},
  year=2004
}