Skip to Main content Skip to Navigation
New interface
Reports (Research report)

A double large prime variation for small genus hyperelliptic index calculus

Pierrick Gaudry 1, 2, 3 Emmanuel Thomé 1 Nicolas Thériault 4 Claus Diem 5 
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/inria-00077334
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 30, 2006 - 2:09:21 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:14 AM
Long-term archiving on: : Monday, April 5, 2010 - 9:49:12 PM

Identifiers

  • HAL Id : inria-00077334, version 1

Collections

Citation

Pierrick Gaudry, Emmanuel Thomé, Nicolas Thériault, Claus Diem. A double large prime variation for small genus hyperelliptic index calculus. [Research Report] RR-5764, INRIA. 2005. ⟨inria-00077334⟩

Share

Metrics

Record views

229

Files downloads

402