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

HTML articles powered by AMS MathViewer

- by
Thorsten Kleinjung and Benjamin Wesolowski
**HTML**| PDF - J. Amer. Math. Soc.
**35**(2022), 581-624 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.

## Additional Information

**Thorsten Kleinjung**- Affiliation: EPFL IC LACAL, Station 14, CH-1015 Lausanne, Switzerland
- MR Author ID: 704259
**Benjamin Wesolowski**- Affiliation: University of Bordeaux, CNRS, Bordeaux INP, IMB, UMR 5251, F-33400, Talence, France; and INRIA, IMB, UMR 5251, F-33400, Talence, France
- MR Author ID: 1163085
- ORCID: 0000-0003-1249-6077
- Received by editor(s): December 4, 2019
- Received by editor(s) in revised form: December 8, 2020, and May 6, 2021
- Published electronically: September 8, 2021
- Additional Notes: Part of this work was supported by the Swiss National Science Foundation under grant number 200021-156420, and by the ERC Advanced Investigator Grant 740972 (ALGSTRONGCRYPTO)
- © Copyright 2021 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**35**(2022), 581-624 - MSC (2020): Primary 11Y16
- DOI: https://doi.org/10.1090/jams/985
- MathSciNet review: 4374957