### A Simplified Approach to Rigorous Degree 2 Elimination in Discrete Logarithm Algorithms

Faruk Göloğlu and Antoine Joux

##### 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}}$.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
discrete logarithm problem
Contact author(s)
farukgologlu @ gmail com
History
Short URL
https://ia.cr/2018/430

CC BY

BibTeX

@misc{cryptoeprint:2018/430,
author = {Faruk  Göloğlu and Antoine Joux},
title = {A Simplified Approach to Rigorous Degree 2 Elimination in Discrete Logarithm Algorithms},
howpublished = {Cryptology ePrint Archive, Paper 2018/430},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/430}},
url = {https://eprint.iacr.org/2018/430}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.