A double large prime variation for small genus hyperelliptic index calculus

Pierrick Gaudry 1, 2, 3 Emmanuel Thomé 3 Nicolas Thériault 4 Claus Diem 5
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
3 CACAO - Curves, Algebra, Computer Arithmetic, and so On
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2007, 76, pp.475-492. 〈10.1090/S0025-5718-06-01900-4〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00000897
Contributeur : Pierrick Gaudry <>
Soumis le : vendredi 2 décembre 2005 - 09:20:07
Dernière modification le : jeudi 10 mai 2018 - 02:06:58
Document(s) archivé(s) le : vendredi 2 avril 2010 - 23:19:01

Fichier

Identifiants

Collections

Citation

Pierrick Gaudry, Emmanuel Thomé, Nicolas Thériault, Claus Diem. A double large prime variation for small genus hyperelliptic index calculus. Mathematics of Computation, American Mathematical Society, 2007, 76, pp.475-492. 〈10.1090/S0025-5718-06-01900-4〉. 〈inria-00000897〉

Partager

Métriques

Consultations de la notice

673

Téléchargements de fichiers

179