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