A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
Faruk Göloğlu, Antoine Joux · Mathematics of Computation · 2018
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 \mathbb {F}_{q^{k_0k}} with k k close to q q and k 0 k_0 a small integer. As in the aforementioned paper, we rely on the existence of two polynomials h 0 h_0 and h 1 h_1 of degree 2 2 providing a convenient representation of the finite field F q k 0 k \mathbb {F}_{q^{k_0k}} .