Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields
HTML articles powered by AMS MathViewer

by M. D. Velichka, M. J. Jacobson Jr. and A. Stein PDF
Math. Comp. 83 (2014), 935-963 Request permission

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
Similar Articles
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
  • MR Author ID: 606532
  • 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
  • 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
  • © Copyright 2013 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Math. Comp. 83 (2014), 935-963
  • MSC (2010): Primary 14G50; Secondary 11G20, 11Y16, 11Y40
  • DOI: https://doi.org/10.1090/S0025-5718-2013-02748-2
  • MathSciNet review: 3143699