Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic

Kleinjung, Thorsten; Wesolowski, Benjamin

doi:10.1090/jams/985

Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic
HTML articles powered by AMS MathViewer

by Thorsten Kleinjung and Benjamin Wesolowski

J. Amer. Math. Soc. 35 (2022), 581-624

DOI: https://doi.org/10.1090/jams/985

Published electronically: September 8, 2021

HTML | PDF | Request permission

Abstract:

We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2\log _2(n) + O(1)}$.

References

Eric Bach, Weil bounds for singular curves, Appl. Algebra Engrg. Comm. Comput. 7 (1996), no. 4, 289–298. MR 1464543, DOI 10.1007/BF01195534
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, Advances in cryptology—EUROCRYPT 2014, Lecture Notes in Comput. Sci., vol. 8441, Springer, Heidelberg, 2014, pp. 1–16. MR 3213210, DOI 10.1007/978-3-642-55220-5_{1}
Jean-Marc Couveignes and Reynald Lercier, Elliptic periods for finite fields, Finite Fields Appl. 15 (2009), no. 1, 1–22. MR 2468989, DOI 10.1016/j.ffa.2008.07.004
Claus Diem, On the discrete logarithm problem in elliptic curves, Compos. Math. 147 (2011), no. 1, 75–104. MR 2771127, DOI 10.1112/S0010437X10005075
Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83–103. MR 1884958, DOI 10.4064/aa102-1-6
William Fulton. Intersection theory, volume 2. Springer Science & Business Media, 2013.
Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc. 370 (2018), no. 5, 3129–3145. MR 3766844, DOI 10.1090/tran/7027
Antoine Joux and Cecile Pierrot, Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms, Preprint, arXiv:1907.02689, 2019.
Thorsten Kleinjung and Benjamin Wesolowski, A new perspective on the powers of two descent for discrete logarithms in finite fields, Proceedings of the Thirteenth Algorithmic Number Theory Symposium, Open Book Ser., vol. 2, Math. Sci. Publ., Berkeley, CA, 2019, pp. 343–352. MR 3952021
Guido Maria Lido, Discrete logarithm over finite fields of “small” characteristic, Master’s thesis, Università di Pisa, Italy, 2016.
Giacomo Micheli, On the selection of polynomials for the DLP quasi-polynomial time algorithm for finite fields of small characteristic, SIAM J. Appl. Algebra Geom. 3 (2019), no. 2, 256–265. MR 3942849, DOI 10.1137/18M1177196
Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
Michael Rosen. Number theory in function fields, volume 210. Springer Science & Business Media, 2013.
Gabriel Daniel Villa Salvador, Topics in the theory of algebraic function fields, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 2006. MR 2241963
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369, DOI 10.24033/asens.1183
Benjamin Wesolowski, Arithmetic and geometric structures in cryptography, PhD thesis, EPFL, 2018.