## On the discrete logarithm problem in finite fields of fixed characteristic

HTML articles powered by AMS MathViewer

- by Robert Granger, Thorsten Kleinjung and Jens Zumbrägel PDF
- Trans. Amer. Math. Soc.
**370**(2018), 3129-3145 Request permission

## Abstract:

For $q$ a prime power, the discrete logarithm problem (DLP) in $\mathbb {F}_{q}$ consists of finding, for any $g \in \mathbb {F}_{q}^{\times }$ and $h \in \langle g \rangle$, an integer $x$ such that $g^x = h$. We present an algorithm for computing discrete logarithms with which we prove that for each prime $p$ there exist infinitely many explicit extension fields $\mathbb {F}_{p^n}$ in which the DLP can be solved in expected quasi-polynomial time. Furthermore, subject to a conjecture on the existence of irreducible polynomials of a certain form, the algorithm solves the DLP in all extensions $\mathbb {F}_{p^n}$ in expected quasi-polynomial time.## References

- Yves Aubry and Marc Perret,
*A Weil theorem for singular curves*, Arithmetic, geometry and coding theory (Luminy, 1993) de Gruyter, Berlin, 1996, pp. 1–7. MR**1394921** - 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} - E. R. Berlekamp,
*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**276200**, DOI 10.1090/S0025-5718-1970-0276200-X - Antonia W. Bluher,
*On $x^{q+1}+ax+b$*, Finite Fields Appl.**10**(2004), no. 3, 285–305. MR**2067599**, DOI 10.1016/j.ffa.2003.08.004 - P. J. Cameron, G. R. Omidi, and B. Tayfeh-Rezaie,
*3-designs from $\textrm {PGL}(2,q)$*, Electron. J. Combin.**13**(2006), no. 1, Research Paper 50, 11. MR**2240756** - Qi Cheng, Daqing Wan, and Jincheng Zhuang,
*Traps to the BGJT-algorithm for discrete logarithms*, LMS J. Comput. Math.**17**(2014), no. suppl. A, 218–229. MR**3240805**, DOI 10.1112/S1461157014000242 - Leonard E. Dickson,
*Linear groups: With an exposition of the Galois field theory*, Teubner, Leipzig, 1901. - 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 - Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel,
*On the function field sieve and the impact of higher splitting probabilities: application to discrete logarithms in $\Bbb F_{2^{1971}}$ and $\Bbb F_{2^{3164}}$*, Advances in cryptology—CRYPTO 2013. Part II, Lecture Notes in Comput. Sci., vol. 8043, Springer, Heidelberg, 2013, pp. 109–128. MR**3126472**, DOI 10.1007/978-3-642-40084-1_{7} - Faruk Göloğlu, Robert Granger, Gary McGuire, and Jens Zumbrägel,
*Solving a 6120-bit DLP on a desktop computer*, Selected Areas in Cryptography—SAC 2013, Lecture Notes in Comput. Sci., vol. 8282, Springer, 2014, pp. 136–152. - Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel,
*Breaking ‘128-bit secure’ supersingular binary curves (or how to solve discrete logarithms in $\Bbb F_{2^{4\cdot 1223}}$ and $\Bbb F_{2^{12\cdot 367}}$)*, Advances in cryptology—CRYPTO 2014. Part II, Lecture Notes in Comput. Sci., vol. 8617, Springer, Heidelberg, 2014, pp. 126–145. MR**3239465**, DOI 10.1007/978-3-662-44381-1_{8} - Tor Helleseth and Alexander Kholosha,
*$x^{2^l+1}+x+a$ and related affine polynomials over $\textrm {GF}(2^k)$*, Cryptogr. Commun.**2**(2010), no. 1, 85–109. MR**2592432**, DOI 10.1007/s12095-009-0018-y - Antoine Joux,
*A new index calculus algorithm with complexity $L(1/4+o(1))$ in small characteristic*, Selected areas in cryptography—SAC 2013, Lecture Notes in Comput. Sci., vol. 8282, Springer, Heidelberg, 2014, pp. 355–379. MR**3218492**, DOI 10.1007/978-3-662-43414-7_{1}8 - Ravindran Kannan and Achim Bachem,
*Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix*, SIAM J. Comput.**8**(1979), no. 4, 499–507. MR**573842**, DOI 10.1137/0208040 - H. W. Lenstra Jr.,
*Finding isomorphisms between finite fields*, Math. Comp.**56**(1991), no. 193, 329–347. MR**1052099**, DOI 10.1090/S0025-5718-1991-1052099-2 - 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 - J. Barkley Rosser and Lowell Schoenfeld,
*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**137689** - Daqing Wan,
*Generators and irreducible polynomials over finite fields*, Math. Comp.**66**(1997), no. 219, 1195–1212. MR**1401947**, DOI 10.1090/S0025-5718-97-00835-1

## Additional Information

**Robert Granger**- Affiliation: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
- MR Author ID: 744248
- Email: robert.granger@epfl.ch
**Thorsten Kleinjung**- Affiliation: Institute of Mathematics, Universität Leipzig, 04109 Leipzig, Germany
- Address at time of publication: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
- MR Author ID: 704259
- Email: thorsten.kleinjung@epfl.ch
**Jens Zumbrägel**- Affiliation: Laboratory for Cryptologic Algorithms, School of Computer and Communication Sciences, École polytechnique fédérale de Lausanne, 1015 Lausanne, Switzerland
- Address at time of publication: Faculty of Computer Science and Mathematics, Universitẗ Passau, 94032 Passau, Germany
- MR Author ID: 843678
- Email: jens.zumbraegel@uni-passau.de
- Received by editor(s): April 27, 2016
- Received by editor(s) in revised form: July 20, 2016
- Published electronically: October 24, 2017
- Additional Notes: The first author was supported by the Swiss National Science Foundation via grant number 200021-156420. This work was mostly done while the second author was with the Laboratory for Cryptologic Algorithms, EPFL, Switzerland, supported by the Swiss National Science Foundation via grant number 200020-132160, and while the third author was with the Institute of Algebra, TU Dresden, Germany, supported by the Irish Research Council via grant number ELEVATEPD/2013/82.
- © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc.
**370**(2018), 3129-3145 - MSC (2010): Primary 11Y16, 11T71
- DOI: https://doi.org/10.1090/tran/7027
- MathSciNet review: 3766844