Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 
 

 

On the discrete logarithm problem in finite fields of fixed characteristic


Authors: Robert Granger, Thorsten Kleinjung and Jens Zumbrägel
Journal: Trans. Amer. Math. Soc.
MSC (2010): Primary 11Y16, 11T71
DOI: https://doi.org/10.1090/tran/7027
Published electronically: October 24, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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
  • [2] 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, https://doi.org/10.1007/978-3-642-55220-5_1
  • [3] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713-735. MR 0276200, https://doi.org/10.2307/2004849
  • [4] Antonia W. Bluher, On $ x^{q+1}+ax+b$, Finite Fields Appl. 10 (2004), no. 3, 285-305. MR 2067599, https://doi.org/10.1016/j.ffa.2003.08.004
  • [5] P. J. Cameron, G. R. Omidi, and B. Tayfeh-Rezaie, 3-designs from $ {\rm PGL}(2,q)$, Electron. J. Combin. 13 (2006), no. 1, Research Paper 50, 11. MR 2240756
  • [6] 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, https://doi.org/10.1112/S1461157014000242
  • [7] Leonard E. Dickson, Linear groups: With an exposition of the Galois field theory, Teubner, Leipzig, 1901.
  • [8] Claus Diem, On the discrete logarithm problem in elliptic curves, Compos. Math. 147 (2011), no. 1, 75-104. MR 2771127, https://doi.org/10.1112/S0010437X10005075
  • [9] Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83-103. MR 1884958, https://doi.org/10.4064/aa102-1-6
  • [10] 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 $ \mathbb{F}_{2^{1971}}$ and $ \mathbb{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, https://doi.org/10.1007/978-3-642-40084-1_7
  • [11] 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.
  • [12] Robert Granger, Thorsten Kleinjung, and Jens Zumbrägel, Breaking `128-bit secure' supersingular binary curves $ ($or how to solve discrete logarithms in $ \mathbb{F}_{2^{4\cdot1223}}$ and $ \mathbb{F}_{2^{12\cdot367}})$, Advances in cryptology--CRYPTO 2014. Part II, Lecture Notes in Comput. Sci., vol. 8617, Springer, Heidelberg, 2014, pp. 126-145. MR 3239465, https://doi.org/10.1007/978-3-662-44381-1_8
  • [13] Tor Helleseth and Alexander Kholosha, $ x^{2^l+1}+x+a$ and related affine polynomials over $ {\rm GF}(2^k)$, Cryptogr. Commun. 2 (2010), no. 1, 85-109. MR 2592432, https://doi.org/10.1007/s12095-009-0018-y
  • [14] 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, https://doi.org/10.1007/978-3-662-43414-7_18
  • [15] 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, https://doi.org/10.1137/0208040
  • [16] H. W. Lenstra Jr., Finding isomorphisms between finite fields, Math. Comp. 56 (1991), no. 193, 329-347. MR 1052099, https://doi.org/10.2307/2008545
  • [17] Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $ {\rm GF}(p)$ and its cryptographic significance, IEEE Trans. Information Theory IT-24 (1978), no. 1, 106-110. MR 0484737
  • [18] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689
  • [19] Daqing Wan, Generators and irreducible polynomials over finite fields, Math. Comp. 66 (1997), no. 219, 1195-1212. MR 1401947, https://doi.org/10.1090/S0025-5718-97-00835-1

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 11Y16, 11T71

Retrieve articles in all journals with MSC (2010): 11Y16, 11T71


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
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
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
Email: jens.zumbraegel@uni-passau.de

DOI: https://doi.org/10.1090/tran/7027
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.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society