May  2018, 12(2): 263-286. doi: 10.3934/amc.2018017

Indiscreet logarithms in finite fields of small characteristic

1. 

Laboratory for Cryptologic Algorithms, École polytechnique fédérale de Lausanne, Station 14, 1015 Lausanne, Switzerland

2. 

Faculty of Computer Science and Mathematics, University of Passau, Innstraße 33, 94032 Passau, Germany

Received  April 2016 Revised  December 2017 Published  March 2018

Fund Project: The first author is supported by the Swiss National Science Foundation via grant number 200021-156420

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.

Citation: Robert Granger, Thorsten Kleinjung, Jens Zumbrägel. Indiscreet logarithms in finite fields of small characteristic. Advances in Mathematics of Communications, 2018, 12 (2) : 263-286. doi: 10.3934/amc.2018017
References:
[1]

G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 509\;\;}}$ for discrete logarithm cryptography, in: Pairing-Based Cryptography—Pairing 2013, Springer, LNCS 8365 (2014), 20–44.  Google Scholar

[2]

G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Computing discrete logarithms in $\mathbb{F}_{3^{6 · 137}}\;\;$ and $\mathbb{F}_{3^{6 · 163}}\;\;$ using Magma, in: Arithmetic of Finite Fields, Springer, LNCS 9061 (2015), 3–22.  Google Scholar

[3]

G. Adj, I. Canales-Martínez, N. Cruz-Cortés, A. Menezes, T. Oliveira, L. RiveraZamarripa and F. Rodríguez-Henríquez, Computing discrete logarithms in cryptographicallyinteresting characteristic-three finite fields, IACR Cryptology ePrint Archive, (2016), 19 pages, eprint. iacr. org/2016/914. Google Scholar

[4]

L. M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, in: 20th Annual Symposium on Foundations of Computer Science, (1979), 55–60. Google Scholar

[5]

L. M. Adleman, The function field sieve, in: Algorithmic Number Theory, Springer, LNCS 877 (1994), 108–121.  Google Scholar

[6]

L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inform. and Comput., 151 (1999), 5-16.  doi: 10.1006/inco.1998.2761.  Google Scholar

[7]

R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann (the CARAMEL group), Discrete logarithm in GF(2809) with FFS, in: Public-Key Cryptography—PKC 2014, Springer, LNCS 8383 (2014), 221–238.  Google Scholar

[8]

R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, in: Advances in Cryptology—EUROCRYPT 2015, Springer, LNCS 9056 (2015), 129–155.  Google Scholar

[9]

R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in: Advances in Cryptology—EUROCRYPT 2014, Springer, LNCS 8441 (2014), 1–16.  Google Scholar

[10]

R. Barbulescu, P. Gaudry and T. Kleinjung, The Tower Number Field Sieve, in: Advances in Cryptology—ASIACRYPT 2015, Springer, LNCS 9453 (2015), 31–55.  Google Scholar

[11]

R. Barbulescu and T. Kim, Extended tower number field sieve: A new complexity for the medium prime case, in: Advances in Cryptology—CRYPTO 2016, Springer, LNCS 9814 (2016), 543–571.  Google Scholar

[12]

A. W. Bluher, On $x^{q+1} + a x + b$, Finite Fields Appl., 10 (2004), 285-305.  doi: 10.1016/j.ffa.2003.08.004.  Google Scholar

[13]

D. Boneh and M. Frapringer, LNCS 2139 (2001nklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology—CRYPTO 2001, S), 213–229.  Google Scholar

[14]

E. R. CanfieldP. Erdős and C. Pomerance, On a problem of Oppenheim concerning 'factorisatio numerorum', J. Number Theory, 17 (1983), 1-28.  doi: 10.1016/0022-314X(83)90002-1.  Google Scholar

[15]

A. Commeine and I. Semaev, An algorithm to solve the discrete logarithm problem with the number field sieve, in: Public Key Cryptography—PKC 2006, Springer, LNCS 3958 (2006), 174–190.  Google Scholar

[16]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594.  doi: 10.1109/TIT.1984.1056941.  Google Scholar

[17]

C. Diem, On the discrete logarithm problem in elliptic curves, Compositio Math., 147 (2011), 75-104.  doi: 10.1112/S0010437X10005075.  Google Scholar

[18]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654.  doi: 10.1109/TIT.1976.1055638.  Google Scholar

[19]

T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in: Advances in Cryptology—CRYPTO '84, Springer, LNCS 196 (1985), 10–18.  Google Scholar

[20]

A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arithmetica, 102 (2002), 83-103.  doi: 10.4064/aa102-1-6.  Google Scholar

[21]

S. D. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology—ASIACRYPT 2001, Springer, LNCS 2248 (2001), 495–513.  Google Scholar

[22]

C. F. Gauß, Disquisitiones Arithmeticae, Translated into English by Arthur A. Clarke, S. J. Yale University Press, New Haven, Conn. -London, 1966.  Google Scholar

[23]

F. Göloğlu, R. Granger, G. McGuire and J. 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}}\;\;$, in: Advances in Cryptology—CRYPTO 2013, Springer, LNCS 8043 (2013), 109–128.  Google Scholar

[24]

F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, Solving a 6120-bit DLP on a desktop computer, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 136–152. Google Scholar

[25]

D. M. Gordon, Discrete logarithms in ${\rm GF}(p)$ using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138.  doi: 10.1137/0406010.  Google Scholar

[26]

D. M. Gordon and K. S. McCurley, Massively parallel computation of discrete logarithms, in: Advances in Cryptology—CRYPTO'92, Springer, LNCS 740 (1993), 312–323. Google Scholar

[27]

R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves, in: Advances in Cryptology—CRYPTO 2014, Springer, LNCS 8617 (2014), 126–145.  Google Scholar

[28]

R. Granger, T. Kleinjung and J. Zumbrägel, On the powers of 2, IACR Cryptology ePrint Archive, (2014), 18 pages, eprint. iacr. org/2014/300. Google Scholar

[29]

R. GrangerT. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc., 370 (2018), 3129-3145.  doi: 10.1090/tran/7027.  Google Scholar

[30]

T. Hayashi, T. Shimoyama, N. Shinohara, T. Takagi, Breaking pairing-based cryptosystems using ηT pairing over GF(397), in: Advances in Cryptology—ASIACRYPT 2012, Springer, LNCS 7658 (2012), 43–60. Google Scholar

[31]

T. Hayashi, N. Shinohara, L. Wang, S. I. Matsuo, M. Shirase and T. Takagi, Solving a 676-bit discrete logarithm problem in GF(36n), in: Public Key Cryptography—PKC 2010, Springer, LNCS 6056 (2010), 351–367.  Google Scholar

[32]

T. Helleseth and A. Kholosha, $\smash{x^{2^l+1}}+ x + a$ and related affine polynomials over $GF(2^k)$, Cryptogr. Commun., 2 (2010), 85-109.  doi: 10.1007/s12095-009-0018-y.  Google Scholar

[33]

A. Joux, A one round protocol for tripartite Diffie-Hellman, in: Algorithmic Number Theory, Springer, LNCS 1838 (2000), 385–393.  Google Scholar

[34]

A. Joux, Faster index calculus for the medium prime case; application to 1175-bit and 1425-bit finite fields, in: Advances in Cryptology—EUROCRYPT 2013, Springer, LNCS 7881 (2013), 177–193.  Google Scholar

[35]

A. Joux, A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 355–379.  Google Scholar

[36]

A. Joux and R. Lercier, The function field sieve is quite special, in: Algorithmic Number Theory, Springer, LNCS 2369 (2002), 431–445.  Google Scholar

[37]

A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields, Math. Comp., 72 (2003), 953-967.  doi: 10.1090/S0025-5718-02-01482-5.  Google Scholar

[38]

A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology—EUROCRYPT 2006, Springer, LNCS 4004 (2006), 254–270.  Google Scholar

[39]

A. Joux, R. Lercier, N. Smart and F. Vercauteren, The number field sieve in the medium prime case, in: Advances in Cryptology—CRYPTO 2006, Springer, LNCS 4117 (2006), 326–344.  Google Scholar

[40]

A. Joux, A. M. Odlyzko and C. Pierrot, The past, evolving present and future of discrete logarithm, in: Open Problems in Mathematical and Computational Science, Springer (2014), 5–36.  Google Scholar

[41]

A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology—ASIACRYPT 2014, Springer, LNCS 8873 (2014), 378–397.  Google Scholar

[42]

M. Kalkbrener, An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries, Mathematica Pannonica, 8 (1997), 73-82.   Google Scholar

[43]

T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, Public-Key Cryptography---PKC 2017, 10174 (2017), 388-408.   Google Scholar

[44]

B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, in: Advances in Cryptology—CRYPTO'90, Springer, LNCS 537 (1991), 109–133. Google Scholar

[45]

C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards, 45 (1950), 255-282.  doi: 10.6028/jres.045.026.  Google Scholar

[46]

A. K. Lenstra and H. W. Lenstra, Jr, Algorithms in number theory, in: Handbook of Theoretical Computer Science (A): Algorithms and Complexity, Elsevier, (1990), 673–715.  Google Scholar

[47]

A. K. Lenstra and H. W. Lenstra, Jr (eds), The Development of the Number Field Sieve, Springer, 1993.  Google Scholar

[48]

A. K. LenstraH. W. Lenstra Jr and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.  Google Scholar

[49]

H. W. Lenstra Jr, Finding isomorphisms between finite fields, Math. Comp., 56 (1991), 329-347.  doi: 10.1090/S0025-5718-1991-1052099-2.  Google Scholar

[50]

R. Lovorn, Rigorous Subexponential Algorithms for Discrete Logarithms over Finite Fields, Ph. D. Thesis, University of Georgia, 1992.  Google Scholar

[51]

V. I. Nechaev, On the complexity of a deterministic algorithm for a discrete logarithm, Mat. Zametki, 55 (1994), 91-101.  doi: 10.1007/BF02113297.  Google Scholar

[52]

J. Neukirch, Algebraic Number Theory, Translated from the 1992 German original, Springer, 1999.  Google Scholar

[53]

A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, in: Advances in Cryptology—CRYPTO'84, Springer, LNCS 209 (1985), 224–314.  Google Scholar

[54]

A. M. Odlyzko, Discrete logarithms: the past and the future, Des. Codes Cryptogr., 19 (2000), 129-145.  doi: 10.1023/A:1008350005447.  Google Scholar

[55]

S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over ${\rm GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110.  doi: 10.1109/TIT.1978.1055817.  Google Scholar

[56]

J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.  doi: 10.1090/S0025-5718-1978-0491431-9.  Google Scholar

[57]

C. Pomerance, Analysis and comparison of some integer factoring algorithms, in: Computational Methods in Number Theory, Math. Centre Tracts, Math. Centrum, Amsterdam, 154 (1982), 89–139.  Google Scholar

[58]

C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, in: Discrete Algorithms and Complexity, Perspect. Comput., Academic Press, 15 (1987), 119–143.  Google Scholar

[59]

R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing, in: Symposium on Cryptography and Information Security, Okinawa, Japan, (2000), 26–28. Google Scholar

[60]

P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, in: Advances in Cryptology—ASIACRYPT 2016, Springer, LNCS 10031 (2016), 37–62.  Google Scholar

[61]

O. Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A, 345 (1993), 409-423.  doi: 10.1098/rsta.1993.0139.  Google Scholar

[62]

O. Schirokauer, Using number fields to compute logarithms in finite fields, Math. Comp., 69 (2000), 1267-1283.  doi: 10.1090/S0025-5718-99-01137-0.  Google Scholar

[63]

O. Schirokauer, Virtual logarithms, J. Algorithms, 57 (2005), 140-147.  doi: 10.1016/j.jalgor.2004.11.004.  Google Scholar

[64]

C.-P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174.  doi: 10.1007/BF00196725.  Google Scholar

[65]

I. A. Semaev, Special prime numbers and discrete logs in finite prime fields, Math. Comp., 71 (2002), 363-377.  doi: 10.1090/S0025-5718-00-01308-9.  Google Scholar

[66]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Computing J., 26 (1997), 1484-1509.  doi: 10.1137/S0097539795293172.  Google Scholar

[67]

V. Shoup, Lower bounds for discrete logarithms and related problems, in: Advances in Cryptology—EUROCRYPT'97, Springer, LNCS 1223 (1997), 256–266.  Google Scholar

[68]

D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212.  doi: 10.1090/S0025-5718-97-00835-1.  Google Scholar

[69]

D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32 (1986), 54-62.  doi: 10.1109/TIT.1986.1057137.  Google Scholar

show all references

References:
[1]

G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 509\;\;}}$ for discrete logarithm cryptography, in: Pairing-Based Cryptography—Pairing 2013, Springer, LNCS 8365 (2014), 20–44.  Google Scholar

[2]

G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Computing discrete logarithms in $\mathbb{F}_{3^{6 · 137}}\;\;$ and $\mathbb{F}_{3^{6 · 163}}\;\;$ using Magma, in: Arithmetic of Finite Fields, Springer, LNCS 9061 (2015), 3–22.  Google Scholar

[3]

G. Adj, I. Canales-Martínez, N. Cruz-Cortés, A. Menezes, T. Oliveira, L. RiveraZamarripa and F. Rodríguez-Henríquez, Computing discrete logarithms in cryptographicallyinteresting characteristic-three finite fields, IACR Cryptology ePrint Archive, (2016), 19 pages, eprint. iacr. org/2016/914. Google Scholar

[4]

L. M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, in: 20th Annual Symposium on Foundations of Computer Science, (1979), 55–60. Google Scholar

[5]

L. M. Adleman, The function field sieve, in: Algorithmic Number Theory, Springer, LNCS 877 (1994), 108–121.  Google Scholar

[6]

L. M. Adleman and M.-D. A. Huang, Function field sieve method for discrete logarithms over finite fields, Inform. and Comput., 151 (1999), 5-16.  doi: 10.1006/inco.1998.2761.  Google Scholar

[7]

R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thomé, M. Videau and P. Zimmermann (the CARAMEL group), Discrete logarithm in GF(2809) with FFS, in: Public-Key Cryptography—PKC 2014, Springer, LNCS 8383 (2014), 221–238.  Google Scholar

[8]

R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, in: Advances in Cryptology—EUROCRYPT 2015, Springer, LNCS 9056 (2015), 129–155.  Google Scholar

[9]

R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, in: Advances in Cryptology—EUROCRYPT 2014, Springer, LNCS 8441 (2014), 1–16.  Google Scholar

[10]

R. Barbulescu, P. Gaudry and T. Kleinjung, The Tower Number Field Sieve, in: Advances in Cryptology—ASIACRYPT 2015, Springer, LNCS 9453 (2015), 31–55.  Google Scholar

[11]

R. Barbulescu and T. Kim, Extended tower number field sieve: A new complexity for the medium prime case, in: Advances in Cryptology—CRYPTO 2016, Springer, LNCS 9814 (2016), 543–571.  Google Scholar

[12]

A. W. Bluher, On $x^{q+1} + a x + b$, Finite Fields Appl., 10 (2004), 285-305.  doi: 10.1016/j.ffa.2003.08.004.  Google Scholar

[13]

D. Boneh and M. Frapringer, LNCS 2139 (2001nklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology—CRYPTO 2001, S), 213–229.  Google Scholar

[14]

E. R. CanfieldP. Erdős and C. Pomerance, On a problem of Oppenheim concerning 'factorisatio numerorum', J. Number Theory, 17 (1983), 1-28.  doi: 10.1016/0022-314X(83)90002-1.  Google Scholar

[15]

A. Commeine and I. Semaev, An algorithm to solve the discrete logarithm problem with the number field sieve, in: Public Key Cryptography—PKC 2006, Springer, LNCS 3958 (2006), 174–190.  Google Scholar

[16]

D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Trans. Inform. Theory, 30 (1984), 587-594.  doi: 10.1109/TIT.1984.1056941.  Google Scholar

[17]

C. Diem, On the discrete logarithm problem in elliptic curves, Compositio Math., 147 (2011), 75-104.  doi: 10.1112/S0010437X10005075.  Google Scholar

[18]

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory, 22 (1976), 644-654.  doi: 10.1109/TIT.1976.1055638.  Google Scholar

[19]

T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, in: Advances in Cryptology—CRYPTO '84, Springer, LNCS 196 (1985), 10–18.  Google Scholar

[20]

A. Enge and P. Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arithmetica, 102 (2002), 83-103.  doi: 10.4064/aa102-1-6.  Google Scholar

[21]

S. D. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology—ASIACRYPT 2001, Springer, LNCS 2248 (2001), 495–513.  Google Scholar

[22]

C. F. Gauß, Disquisitiones Arithmeticae, Translated into English by Arthur A. Clarke, S. J. Yale University Press, New Haven, Conn. -London, 1966.  Google Scholar

[23]

F. Göloğlu, R. Granger, G. McGuire and J. 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}}\;\;$, in: Advances in Cryptology—CRYPTO 2013, Springer, LNCS 8043 (2013), 109–128.  Google Scholar

[24]

F. Göloğlu, R. Granger, G. McGuire and J. Zumbrägel, Solving a 6120-bit DLP on a desktop computer, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 136–152. Google Scholar

[25]

D. M. Gordon, Discrete logarithms in ${\rm GF}(p)$ using the number field sieve, SIAM J. Discrete Math., 6 (1993), 124-138.  doi: 10.1137/0406010.  Google Scholar

[26]

D. M. Gordon and K. S. McCurley, Massively parallel computation of discrete logarithms, in: Advances in Cryptology—CRYPTO'92, Springer, LNCS 740 (1993), 312–323. Google Scholar

[27]

R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves, in: Advances in Cryptology—CRYPTO 2014, Springer, LNCS 8617 (2014), 126–145.  Google Scholar

[28]

R. Granger, T. Kleinjung and J. Zumbrägel, On the powers of 2, IACR Cryptology ePrint Archive, (2014), 18 pages, eprint. iacr. org/2014/300. Google Scholar

[29]

R. GrangerT. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Trans. Amer. Math. Soc., 370 (2018), 3129-3145.  doi: 10.1090/tran/7027.  Google Scholar

[30]

T. Hayashi, T. Shimoyama, N. Shinohara, T. Takagi, Breaking pairing-based cryptosystems using ηT pairing over GF(397), in: Advances in Cryptology—ASIACRYPT 2012, Springer, LNCS 7658 (2012), 43–60. Google Scholar

[31]

T. Hayashi, N. Shinohara, L. Wang, S. I. Matsuo, M. Shirase and T. Takagi, Solving a 676-bit discrete logarithm problem in GF(36n), in: Public Key Cryptography—PKC 2010, Springer, LNCS 6056 (2010), 351–367.  Google Scholar

[32]

T. Helleseth and A. Kholosha, $\smash{x^{2^l+1}}+ x + a$ and related affine polynomials over $GF(2^k)$, Cryptogr. Commun., 2 (2010), 85-109.  doi: 10.1007/s12095-009-0018-y.  Google Scholar

[33]

A. Joux, A one round protocol for tripartite Diffie-Hellman, in: Algorithmic Number Theory, Springer, LNCS 1838 (2000), 385–393.  Google Scholar

[34]

A. Joux, Faster index calculus for the medium prime case; application to 1175-bit and 1425-bit finite fields, in: Advances in Cryptology—EUROCRYPT 2013, Springer, LNCS 7881 (2013), 177–193.  Google Scholar

[35]

A. Joux, A new index calculus algorithm with complexity L(1/4 + o(1)) in small characteristic, in: Selected Areas in Cryptography—SAC 2013, Springer, LNCS 8282 (2014), 355–379.  Google Scholar

[36]

A. Joux and R. Lercier, The function field sieve is quite special, in: Algorithmic Number Theory, Springer, LNCS 2369 (2002), 431–445.  Google Scholar

[37]

A. Joux and R. Lercier, Improvements to the general number field sieve for discrete logarithms in prime fields, Math. Comp., 72 (2003), 953-967.  doi: 10.1090/S0025-5718-02-01482-5.  Google Scholar

[38]

A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology—EUROCRYPT 2006, Springer, LNCS 4004 (2006), 254–270.  Google Scholar

[39]

A. Joux, R. Lercier, N. Smart and F. Vercauteren, The number field sieve in the medium prime case, in: Advances in Cryptology—CRYPTO 2006, Springer, LNCS 4117 (2006), 326–344.  Google Scholar

[40]

A. Joux, A. M. Odlyzko and C. Pierrot, The past, evolving present and future of discrete logarithm, in: Open Problems in Mathematical and Computational Science, Springer (2014), 5–36.  Google Scholar

[41]

A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology—ASIACRYPT 2014, Springer, LNCS 8873 (2014), 378–397.  Google Scholar

[42]

M. Kalkbrener, An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries, Mathematica Pannonica, 8 (1997), 73-82.   Google Scholar

[43]

T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, Public-Key Cryptography---PKC 2017, 10174 (2017), 388-408.   Google Scholar

[44]

B. A. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, in: Advances in Cryptology—CRYPTO'90, Springer, LNCS 537 (1991), 109–133. Google Scholar

[45]

C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards, 45 (1950), 255-282.  doi: 10.6028/jres.045.026.  Google Scholar

[46]

A. K. Lenstra and H. W. Lenstra, Jr, Algorithms in number theory, in: Handbook of Theoretical Computer Science (A): Algorithms and Complexity, Elsevier, (1990), 673–715.  Google Scholar

[47]

A. K. Lenstra and H. W. Lenstra, Jr (eds), The Development of the Number Field Sieve, Springer, 1993.  Google Scholar

[48]

A. K. LenstraH. W. Lenstra Jr and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann., 261 (1982), 515-534.  doi: 10.1007/BF01457454.  Google Scholar

[49]

H. W. Lenstra Jr, Finding isomorphisms between finite fields, Math. Comp., 56 (1991), 329-347.  doi: 10.1090/S0025-5718-1991-1052099-2.  Google Scholar

[50]

R. Lovorn, Rigorous Subexponential Algorithms for Discrete Logarithms over Finite Fields, Ph. D. Thesis, University of Georgia, 1992.  Google Scholar

[51]

V. I. Nechaev, On the complexity of a deterministic algorithm for a discrete logarithm, Mat. Zametki, 55 (1994), 91-101.  doi: 10.1007/BF02113297.  Google Scholar

[52]

J. Neukirch, Algebraic Number Theory, Translated from the 1992 German original, Springer, 1999.  Google Scholar

[53]

A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, in: Advances in Cryptology—CRYPTO'84, Springer, LNCS 209 (1985), 224–314.  Google Scholar

[54]

A. M. Odlyzko, Discrete logarithms: the past and the future, Des. Codes Cryptogr., 19 (2000), 129-145.  doi: 10.1023/A:1008350005447.  Google Scholar

[55]

S. C. Pohlig and M. E. Hellman, An improved algorithm for computing logarithms over ${\rm GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110.  doi: 10.1109/TIT.1978.1055817.  Google Scholar

[56]

J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32 (1978), 918-924.  doi: 10.1090/S0025-5718-1978-0491431-9.  Google Scholar

[57]

C. Pomerance, Analysis and comparison of some integer factoring algorithms, in: Computational Methods in Number Theory, Math. Centre Tracts, Math. Centrum, Amsterdam, 154 (1982), 89–139.  Google Scholar

[58]

C. Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, in: Discrete Algorithms and Complexity, Perspect. Comput., Academic Press, 15 (1987), 119–143.  Google Scholar

[59]

R. Sakai, K. Ohgishi and M. Kasahara, Cryptosystems based on pairing, in: Symposium on Cryptography and Information Security, Okinawa, Japan, (2000), 26–28. Google Scholar

[60]

P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, in: Advances in Cryptology—ASIACRYPT 2016, Springer, LNCS 10031 (2016), 37–62.  Google Scholar

[61]

O. Schirokauer, Discrete logarithms and local units, Philos. Trans. Roy. Soc. London Ser. A, 345 (1993), 409-423.  doi: 10.1098/rsta.1993.0139.  Google Scholar

[62]

O. Schirokauer, Using number fields to compute logarithms in finite fields, Math. Comp., 69 (2000), 1267-1283.  doi: 10.1090/S0025-5718-99-01137-0.  Google Scholar

[63]

O. Schirokauer, Virtual logarithms, J. Algorithms, 57 (2005), 140-147.  doi: 10.1016/j.jalgor.2004.11.004.  Google Scholar

[64]

C.-P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, 4 (1991), 161-174.  doi: 10.1007/BF00196725.  Google Scholar

[65]

I. A. Semaev, Special prime numbers and discrete logs in finite prime fields, Math. Comp., 71 (2002), 363-377.  doi: 10.1090/S0025-5718-00-01308-9.  Google Scholar

[66]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Computing J., 26 (1997), 1484-1509.  doi: 10.1137/S0097539795293172.  Google Scholar

[67]

V. Shoup, Lower bounds for discrete logarithms and related problems, in: Advances in Cryptology—EUROCRYPT'97, Springer, LNCS 1223 (1997), 256–266.  Google Scholar

[68]

D. Wan, Generators and irreducible polynomials over finite fields, Math. Comp., 66 (1997), 1195-1212.  doi: 10.1090/S0025-5718-97-00835-1.  Google Scholar

[69]

D. H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32 (1986), 54-62.  doi: 10.1109/TIT.1986.1057137.  Google Scholar

Table 1.  Discrete logarithm record computations in finite fields of small or medium characteristic. Details, as well as further announcements, can be found in the number theory mailing list (https://listserv.nodak.edu/cgi-bin/wa.exe?A0=NMBRTHRY)
bitlengthcharact.Kummerwho/whenrunning time
1272noCoppersmith 1984 [16] $L(1/3\, , \, 1.526..1.587)$
4012noGordon, McCurley 1992 [26] $L(1/3\, , \, 1.526..1.587)$
5212noJoux, Lercier 2001 [36] $L(1/3\, , \, 1.526)$
6072noThomé 2002 $L(1/3\, , \, 1.526..1.587)$
6132noJoux, Lercier 2005 $L(1/3\, , \, 1.526)$
556mediumyesJoux, Lercier 2006 [38] $L(1/3\, , \, 1.442)$
6763noHayashi et al. 2010 [31] $L(1/3\, , \, 1.442)$
9233noHayashi et al. 2012 [30] $L(1/3\, , \, 1.442)$
1175mediumyesJoux 24 Dec 2012 [34] $L(1/3\, , \, 1.260)$
1425mediumyesJoux 6 Jan 2013 [34] $L(1/3\, , \, 1.260)$
17782yesJoux 11 Feb 2013 [35] $L(1/4 + o(1))$
19712yesGGMZ 19 Feb 2013 [23] $L(1/3\, , \, 0.763)$
40802yesJoux 22 Mar 2013 [35] $L(1/4 + o(1))$
8092noCARAMEL 6 Apr 2013 [7] $L(1/3\, , \, 1.526)$
61202yesGGMZ 11 Apr 2013 [24] $L(1/4)$
61682yesJoux 21 May 2013 $L(1/4 + o(1))$
13033noAMOR 27 Jan 2014 [2] $L(1/4 + o(1))$
44042noGKZ 30 Jan 2014 [27] $L(1/4 + o(1))$
92342yesGKZ 31 Jan 2014 $L(1/4 + o(1))$
15513noAMOR 26 Feb 2014 [2] $L(1/4 + o(1))$
37963noJoux, Pierrot 15 Sep 2014 [41] $L(0 + o(1))$
12792noKleinjung 17 Oct 2014 $L(0 + o(1))$
48413noACCMORR, 18 Jul 2016 [3] $L(0 + o(1))$
bitlengthcharact.Kummerwho/whenrunning time
1272noCoppersmith 1984 [16] $L(1/3\, , \, 1.526..1.587)$
4012noGordon, McCurley 1992 [26] $L(1/3\, , \, 1.526..1.587)$
5212noJoux, Lercier 2001 [36] $L(1/3\, , \, 1.526)$
6072noThomé 2002 $L(1/3\, , \, 1.526..1.587)$
6132noJoux, Lercier 2005 $L(1/3\, , \, 1.526)$
556mediumyesJoux, Lercier 2006 [38] $L(1/3\, , \, 1.442)$
6763noHayashi et al. 2010 [31] $L(1/3\, , \, 1.442)$
9233noHayashi et al. 2012 [30] $L(1/3\, , \, 1.442)$
1175mediumyesJoux 24 Dec 2012 [34] $L(1/3\, , \, 1.260)$
1425mediumyesJoux 6 Jan 2013 [34] $L(1/3\, , \, 1.260)$
17782yesJoux 11 Feb 2013 [35] $L(1/4 + o(1))$
19712yesGGMZ 19 Feb 2013 [23] $L(1/3\, , \, 0.763)$
40802yesJoux 22 Mar 2013 [35] $L(1/4 + o(1))$
8092noCARAMEL 6 Apr 2013 [7] $L(1/3\, , \, 1.526)$
61202yesGGMZ 11 Apr 2013 [24] $L(1/4)$
61682yesJoux 21 May 2013 $L(1/4 + o(1))$
13033noAMOR 27 Jan 2014 [2] $L(1/4 + o(1))$
44042noGKZ 30 Jan 2014 [27] $L(1/4 + o(1))$
92342yesGKZ 31 Jan 2014 $L(1/4 + o(1))$
15513noAMOR 26 Feb 2014 [2] $L(1/4 + o(1))$
37963noJoux, Pierrot 15 Sep 2014 [41] $L(0 + o(1))$
12792noKleinjung 17 Oct 2014 $L(0 + o(1))$
48413noACCMORR, 18 Jul 2016 [3] $L(0 + o(1))$
[1]

Palash Sarkar, Shashank Singh. A unified polynomial selection method for the (tower) number field sieve algorithm. Advances in Mathematics of Communications, 2019, 13 (3) : 435-455. doi: 10.3934/amc.2019028

[2]

Carla Mascia, Giancarlo Rinaldo, Massimiliano Sala. Hilbert quasi-polynomial for order domains and application to coding theory. Advances in Mathematics of Communications, 2018, 12 (2) : 287-301. doi: 10.3934/amc.2018018

[3]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks & Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263

[4]

Laurent Imbert, Michael J. Jacobson, Jr., Arthur Schmidt. Fast ideal cubing in imaginary quadratic number and function fields. Advances in Mathematics of Communications, 2010, 4 (2) : 237-260. doi: 10.3934/amc.2010.4.237

[5]

Josu Doncel, Nicolas Gast, Bruno Gaujal. Discrete mean field games: Existence of equilibria and convergence. Journal of Dynamics & Games, 2019, 6 (3) : 221-239. doi: 10.3934/jdg.2019016

[6]

László Mérai, Igor E. Shparlinski. Unlikely intersections over finite fields: Polynomial orbits in small subgroups. Discrete & Continuous Dynamical Systems - A, 2020, 40 (2) : 1065-1073. doi: 10.3934/dcds.2020070

[7]

Fabio Camilli, Elisabetta Carlini, Claudio Marchi. A model problem for Mean Field Games on networks. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4173-4192. doi: 10.3934/dcds.2015.35.4173

[8]

Yves Achdou, Victor Perez. Iterative strategies for solving linearized discrete mean field games systems. Networks & Heterogeneous Media, 2012, 7 (2) : 197-217. doi: 10.3934/nhm.2012.7.197

[9]

Juan Pablo Maldonado López. Discrete time mean field games: The short-stage limit. Journal of Dynamics & Games, 2015, 2 (1) : 89-101. doi: 10.3934/jdg.2015.2.89

[10]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010

[11]

Santos González, Llorenç Huguet, Consuelo Martínez, Hugo Villafañe. Discrete logarithm like problems and linear recurring sequences. Advances in Mathematics of Communications, 2013, 7 (2) : 187-195. doi: 10.3934/amc.2013.7.187

[12]

Juan Li, Wenqiang Li. Controlled reflected mean-field backward stochastic differential equations coupled with value function and related PDEs. Mathematical Control & Related Fields, 2015, 5 (3) : 501-516. doi: 10.3934/mcrf.2015.5.501

[13]

Maria Schonbek, Tomas Schonbek. Moments and lower bounds in the far-field of solutions to quasi-geostrophic flows. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1277-1304. doi: 10.3934/dcds.2005.13.1277

[14]

Ekkasit Sangwisut, Somphong Jitman, Patanee Udomkavanich. Constacyclic and quasi-twisted Hermitian self-dual codes over finite fields. Advances in Mathematics of Communications, 2017, 11 (3) : 595-613. doi: 10.3934/amc.2017045

[15]

Nguyen Huy Chieu, Jen-Chih Yao. Subgradients of the optimal value function in a parametric discrete optimal control problem. Journal of Industrial & Management Optimization, 2010, 6 (2) : 401-410. doi: 10.3934/jimo.2010.6.401

[16]

Antoni Ferragut, Jaume Llibre, Adam Mahdi. Polynomial inverse integrating factors for polynomial vector fields. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 387-395. doi: 10.3934/dcds.2007.17.387

[17]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[18]

Keisuke Hakuta, Hisayoshi Sato, Tsuyoshi Takagi. On tameness of Matsumoto-Imai central maps in three variables over the finite field $\mathbb F_2$. Advances in Mathematics of Communications, 2016, 10 (2) : 221-228. doi: 10.3934/amc.2016002

[19]

Tetsuya Ishiwata, Kota Kumazaki. Structure preserving finite difference scheme for the Landau-Lifshitz equation with applied magnetic field. Conference Publications, 2015, 2015 (special) : 644-651. doi: 10.3934/proc.2015.0644

[20]

Yi Shi, Kai Bao, Xiao-Ping Wang. 3D adaptive finite element method for a phase field model for the moving contact line problems. Inverse Problems & Imaging, 2013, 7 (3) : 947-959. doi: 10.3934/ipi.2013.7.947

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (111)
  • HTML views (309)
  • Cited by (0)

[Back to Top]