Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

   
 
 

 

A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms


Authors: Faruk Göloğlu and Antoine Joux
Journal: Math. Comp. 88 (2019), 2485-2496
MSC (2010): Primary 11Y16, 12Y05
DOI: https://doi.org/10.1090/mcom/3404
Published electronically: December 31, 2018
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we revisit the ZigZag strategy of Granger, Kleinjung, and Zumbrägel. In particular, we provide a new algorithm and proof for the so-called degree 2 elimination step. This allows us to provide a stronger theorem concerning discrete logarithm computations in small characteristic fields $ \mathbb{F}_{q^{k_0k}}$ with $ k$ close to $ q$ and $ k_0$ a small integer. As in the aforementioned paper, we rely on the existence of two polynomials $ h_0$ and $ h_1$ of degree $ 2$ providing a convenient representation of the finite field  $ \mathbb{F}_{q^{k_0k}}$.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 12Y05

Retrieve articles in all journals with MSC (2010): 11Y16, 12Y05


Additional Information

Faruk Göloğlu
Affiliation: Department of Mathematics, Faculty of Mathematics and Physics, Charles University, Sokolovská 83, 186 75 Praha 8, Czech Republic
Email: farukgologlu@gmail.com

Antoine Joux
Affiliation: Chaire de Cryptologie de la Fondation SU, Sorbonne Université, Institut de Mathématiques de Jussieu–Paris Rive Gauche, CNRS, INRIA, Univ Paris Diderot. Campus Pierre et Marie Curie, F-75005 Paris, France
Email: antoine.joux@m4x.org

DOI: https://doi.org/10.1090/mcom/3404
Received by editor(s): April 16, 2018
Received by editor(s) in revised form: April 20, 2018, and September 4, 2018
Published electronically: December 31, 2018
Additional Notes: This work was supported in part by the European Union’s H2020 Programme under grant agreement number ERC-669891. It has also been supported by GAČR Grant 18-19087S-301-13/201843.
Article copyright: © Copyright 2018 Foruk Göloğlu and Antoine Joux