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

Faruk  Göloğlu; Antoine Joux

Paper 2018/430

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 $F_{q^{k_{0} k}}$ with $k$ close to $q$ and a small integer. As in the aforementioned paper, we rely on the existence of two polynomials and of degree providing a convenient representation of the finite field .

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: discrete logarithm problem
Contact author(s): farukgologlu @ gmail com
History: 2018-05-11: received
Short URL: https://ia.cr/2018/430
License: 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},
      url = {https://eprint.iacr.org/2018/430}
}