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.

[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.

[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.

[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.

[5]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[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.

[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.

[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.

[21]

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

[22]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[33]

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

[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.

[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.

[36]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[47]

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

[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.

[49]

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

[50]

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

[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.

[52]

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

[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.

[54]

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

[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.

[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.

[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.

[58]

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

[59]

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

[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.

[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.

[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.

[63]

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

[64]

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

[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.

[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.

[67]

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

[68]

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

[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.

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.

[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.

[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.

[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.

[5]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17]

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

[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.

[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.

[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.

[21]

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

[22]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[33]

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

[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.

[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.

[36]

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

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[47]

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

[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.

[49]

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

[50]

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

[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.

[52]

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

[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.

[54]

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

[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.

[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.

[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.

[58]

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

[59]

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

[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.

[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.

[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.

[63]

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

[64]

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

[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.

[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.

[67]

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

[68]

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

[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.

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]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Andrew Comech. Weak attractor of the Klein-Gordon field in discrete space-time interacting with a nonlinear oscillator. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2711-2755. doi: 10.3934/dcds.2013.33.2711

[19]

Pavel Krejčí, Elisabetta Rocca, Jürgen Sprekels. Phase separation in a gravity field. Discrete & Continuous Dynamical Systems - S, 2011, 4 (2) : 391-407. doi: 10.3934/dcdss.2011.4.391

[20]

Marco Castrillón López, Mark J. Gotay. Covariantizing classical field theories. Journal of Geometric Mechanics, 2011, 3 (4) : 487-506. doi: 10.3934/jgm.2011.3.487

2016 Impact Factor: 0.8

Article outline

Figures and Tables

[Back to Top]