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
Published electronically: December 31, 2018
MathSciNet review: 3957902
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

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
MR Author ID: 316495

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