Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

   

 

Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields


Authors: M. D. Velichka, M. J. Jacobson Jr. and A. Stein
Journal: Math. Comp. 83 (2014), 935-963
MSC (2010): Primary 14G50; Secondary 11G20, 11Y16, 11Y40
Published electronically: July 23, 2013
MathSciNet review: 3143699
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Thériault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in a 2001 paper by Jacobson, Menzes, and Stein to our new algorithm, allowing us to predict accurately the number of random walk steps required to find all relations, and to select optimal degree bounds for the factor base. Our second improvement is the adaptation of sieving techniques from Flassenberg and Paulus, and Jacobson to our setting. The new algorithms are applied to concrete problem instances arising from the Weil descent attack methodology for solving the elliptic curve discrete logarithm problem, demonstrating significant improvements in practice.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14G50, 11G20, 11Y16, 11Y40

Retrieve articles in all journals with MSC (2010): 14G50, 11G20, 11Y16, 11Y40


Additional Information

M. D. Velichka
Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: markvelichka@gmail.com

M. J. Jacobson Jr.
Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4
Email: jacobs@cpsc.ucalgary.ca

A. Stein
Affiliation: Institut für Mathematik, Carl-von-Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany
Email: andreas.stein1@uni-oldenburg.de

DOI: http://dx.doi.org/10.1090/S0025-5718-2013-02748-2
Keywords: Hyperelliptic curves, discrete logarithm problem, sieving, Weil descent
Received by editor(s): February 7, 2011
Received by editor(s) in revised form: July 3, 2012
Published electronically: July 23, 2013
Additional Notes: The first author’s research was supported by NSERC of Canada
The second author’s research was supported by NSERC of Canada
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.