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

Göloğlu, Faruk; Joux, Antoine

doi:10.1090/mcom/3404

A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
HTML articles powered by AMS MathViewer

by Faruk Göloğlu and Antoine Joux;

Math. Comp. 88 (2019), 2485-2496

DOI: https://doi.org/10.1090/mcom/3404

Published electronically: December 31, 2018

HTML | PDF

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

Leonard M. Adleman and Jonathan DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 61 (1993), no. 203, 1–15. MR 1225541, DOI 10.1090/S0025-5718-1993-1225541-3
R. Granger, T. Kleinjung, and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Cryptology ePrint Archive, Report 2015/685, 2015.
Antoine Joux and Cécile Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms: simplified setting for small characteristic finite fields, Advances in cryptology—ASIACRYPT 2014. Part I, Lecture Notes in Comput. Sci., vol. 8873, Springer, Heidelberg, 2014, pp. 378–397. MR 3297559, DOI 10.1007/978-3-662-45611-8_{2}0
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817