Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A double large prime variation for small genus hyperelliptic index calculus

Authors: P. Gaudry, E. Thomé, N. Thériault and C. Diem
Journal: Math. Comp. 76 (2007), 475-492
MSC (2000): Primary 11Y16; Secondary 11T71, 94A60
Published electronically: October 4, 2006
MathSciNet review: 2261032
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11T71, 94A60

Retrieve articles in all journals with MSC (2000): 11Y16, 11T71, 94A60

Additional Information

P. Gaudry
Affiliation: École polytechnique, LIX, 91128 Palaiseau Cedex, France

E. Thomé
Affiliation: INRIA Lorraine, SPACES, 615 rue du Jardin botanique, 54602 Villers-Lès-Nancy Cedex, France

N. Thériault
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, N2L 3G1 Canada

C. Diem
Affiliation: Faculty for Mathematics and Informatics, University of Leipzig, Augustusplatz 10-11, 04109 Leipzig, Germany

Received by editor(s): February 16, 2005
Received by editor(s) in revised form: November 21, 2005
Published electronically: October 4, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society