A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms
Authors:
Faruk 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
Published electronically:
December 31, 2018
MathSciNet review:
3957902
Full-text PDF
View in AMS MathViewer
Abstract | References | Similar Articles | Additional Information
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}}$.
- 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 https://doi.org/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 https://doi.org/10.1007/978-3-662-45611-8_20
- Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over ${\rm GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI https://doi.org/10.1109/tit.1978.1055817
Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 12Y05
Retrieve articles in all journals with MSC (2010): 11Y16, 12Y05
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.
Article copyright:
© Copyright 2018
Foruk Göloğlu and Antoine Joux