## 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
**HTML**| PDF - Math. Comp.
**88**(2019), 2485-2496

## 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

## 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
- Email: farukgologlu@gmail.com
**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
- Email: antoine.joux@m4x.org
- 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.
- © Copyright 2018 Foruk Göloğlu and Antoine Joux
- Journal: Math. Comp.
**88**(2019), 2485-2496 - MSC (2010): Primary 11Y16, 12Y05
- DOI: https://doi.org/10.1090/mcom/3404
- MathSciNet review: 3957902