# American Institute of Mathematical Sciences

November  2018, 12(4): 741-759. doi: 10.3934/amc.2018044

## Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields

 1 Computer Science Department, CINVESTAV-IPN, Mexico 2 Centro de Investigación en Computación, Instituto Politécnico Nacional, Mexico 3 Department of Combinatorics & Optimization, University of Waterloo, Canada

Received  November 2017 Published  September 2018

Since 2013 there have been several developments in algorithms for computing discrete logarithms in small-characteristic finite fields, culminating in a quasi-polynomial algorithm. In this paper, we report on our successful computation of discrete logarithms in the cryptographically-interesting characteristic-three finite field $\mathbb{F}_{3^{6.509}}$    using these new algorithms; prior to 2013, it was believed that this field enjoyed a security level of 128 bits. We also show that a recent idea of Guillevic can be used to compute discrete logarithms in the cryptographically-interesting finite field $\mathbb{F}_{3^{6.709}}$    using essentially the same resources as we expended on the $\mathbb{F}_{3^{6.509}}$    computation. Finally, we argue that discrete logarithms in the finite field $\mathbb{F}_{3^{6.1429}}$    can feasibly be computed today; this is significant because this cryptographically-interesting field was previously believed to enjoy a security level of 192 bits.

Citation: Gora Adj, Isaac Canales-Martínez, Nareli Cruz-Cortés, Alfred Menezes, Thomaz Oliveira, Luis Rivera-Zamarripa, Francisco Rodríguez-Henríquez. Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields. Advances in Mathematics of Communications, 2018, 12 (4) : 741-759. doi: 10.3934/amc.2018044
##### References:
 [1] ABACUS Supercomputer - Cinvestav, http://www.abacus.cinvestav.mx/.Google Scholar [2] G. Adj, Logaritmo discreto en campos finitos de característica pequeña: atacando la criptografía basada en emparejamientos de Tipo 1, Ph.D. thesis, CINVESTAV-IPN, 2016. Available at http://www.cs.cinvestav.mx/TesisGraduados/2016/TesisGoraAdj.pdf.Google Scholar [3] 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, LNCS, 8365 (2014), 20-44. doi: 10.1007/978-3-319-04873-4_2. Google Scholar [4] G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 1429}}$    and $\mathbb{F}_{2^{4 · 3041}}$    for discrete logarithm cryptography, Finite Fields and Their Applications, 32 (2015), 148-170. doi: 10.1016/j.ffa.2014.10.009. Google Scholar [5] 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: WAIFI 2014, LNCS, 9061 (2015), 3-22. doi: 10.1007/978-3-319-16277-5_1. Google Scholar [6] R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic: Improvements over FFS in small to medium characteristic, in: Advances in Cryptology - EUROCRYPT 2014, LNCS, 8441 (2014), 1-16. doi: 10.1007/978-3-642-55220-5_1. Google Scholar [7] P. Barreto, S. Galbraith, C. ÓhÉigeartaigh and M. Scott, Efficient pairing computation on supersingular abelian varieties, Designs, Codes and Cryptography, 42 (2007), 239-271. doi: 10.1007/s10623-006-9033-6. Google Scholar [8] P. Barreto, H. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems, in: Advances in Cryptology - CRYPTO 2002, LNCS, 2442 (2002), 354-368. doi: 10.1007/3-540-45708-9_23. Google Scholar [9] I. Blake, R. Fuji-Hara, R. Mullin and S. Vanstone, Computing logarithms in finite fields of characteristic two, SIAM Journal on Algebraic and Discrete Methods, 5 (1984), 276-285. doi: 10.1137/0605029. Google Scholar [10] D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology - CRYPTO 2001, LNCS, 2139 (2001), 213-229. doi: 10.1007/3-540-44647-8_13. Google Scholar [11] D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004), 297-319. doi: 10.1007/s00145-004-0314-9. Google Scholar [12] I. Canales-Martínez, Implementación eficiente de prueba de suavidad para polinomios, Tesis de Maestría, CINVESTAV-IPN, 2015. Available at http://delta.cs.cinvestav.mx/~francisco/Thesis_IAC.pdf.Google Scholar [13] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), 587-594. doi: 10.1109/TIT.1984.1056941. Google Scholar [14] The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/.Google Scholar [15] J. Faugère, A new efficient algorithm for computing Gröbner bases ($F_4$), Journal of Pure and Applied Algebra, 139 (1999), 61-88. doi: 10.1016/S0022-4049(99)00005-5. Google Scholar [16] G. Frey and H. Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62 (1994), 865-874. doi: 10.2307/2153546. Google Scholar [17] S. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology - ASIACRYPT 2001, LNCS 2248 (2001), 495-513. doi: 10.1007/3-540-45682-1_29. Google Scholar [18] S. Galbraith, K. Harrison and D. Soldera, Implementing the Tate pairing, in: Algorithmic Number Theory - ANTS 2002, LNCS, 2369 (2002), 324-337. doi: 10.1007/3-540-45455-1_26. Google Scholar [19] 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}}$ , in: Advances in Cryptology - CRYPTO 2013, LNCS, 8043 (2013), 109-128. doi: 10.1007/978-3-642-40084-1_7. Google Scholar [20] 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 2014, LNC, S 8282 (2014), 136-152.Google Scholar [21] D. Gordon, Discrete logarithms in $GF(p)$ using the number field sieve, SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. doi: 10.1137/0406010. Google Scholar [22] R. Granger, T. Kleinjung and J. Zumbrägel, Breaking 128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$    and $\mathbb{F}_{2^{12 · 367}}$) , in: Advances in Cryptology - CRYPTO 2014, Part II, LNCS, 8617 (2014), 126-145. doi: 10.1007/978-3-662-44381-1_8. Google Scholar [23] R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$    and $\mathbb{F}_{2^{12 · 367}}$) , Cryptology ePrint Archive: Report 2014/119, http://eprint.iacr.org/2014/119.Google Scholar [24] R. Granger, T. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Transactions of the AMS, 370 (2018), 3129-3145. doi: 10.1090/tran/7027. Google Scholar [25] A. Guillevic, Faster individual discrete logarithms with the QPA and NFS variants, Cryptology ePrint Archive: Report 2016/684, https://eprint.iacr.org/2016/684.Google Scholar [26] A. Joux, A new index calculus algorithm with complexity $L(1/4 + o(1))$ in very small characteristic, in: Selected Areas in Cryptography - SAC 2013, LNCS, 8282 (2014), 355-379. doi: 10.1007/978-3-662-43414-7_18. Google Scholar [27] A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology - EUROCRYPT 2006, LNCS, 4004 (2006), 254-270. doi: 10.1007/11761679_16. Google Scholar [28] A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology - ASIACRYPT 2014, LNCS, 8873 (2014), 378-397. doi: 10.1007/978-3-662-45611-8_20. Google Scholar [29] A. Joux and C. Pierrot, Technical history of discrete logarithms in small characteristic finite fields, Designs, Codes and Cryptography, 78 (2016), 73-85. doi: 10.1007/s10623-015-0147-6. Google Scholar [30] A. Knopfmacher and J. Knopfmacher, Counting irreducible factors of polynomials over a finite fields, Discrete Mathematics, 112 (1993), 103-118. doi: 10.1016/0012-365X(93)90227-K. Google Scholar [31] A. Lenstra, Unbelievable security: Matching AES security using public key systems, in: Advances in Cryptology - ASIACRYPT 2001, LNCS, 2248 (2001), 67-86. doi: 10.1007/3-540-45682-1_5. Google Scholar [32] Magma v2.19-7, http://magma.maths.usyd.edu.au/magma/.Google Scholar [33] [34] A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, 39 (1993), 1639-1646. doi: 10.1109/18.259647. Google Scholar [35] O. Schirokauer, Discrete logarithms and local units, Philosophical Transactions of the Royal Society London A, 345 (1993), 409-423. doi: 10.1098/rsta.1993.0139. Google Scholar [36] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, 32 (1986), 54-62. doi: 10.1109/TIT.1986.1057137. Google Scholar

show all references

##### References:
 [1] ABACUS Supercomputer - Cinvestav, http://www.abacus.cinvestav.mx/.Google Scholar [2] G. Adj, Logaritmo discreto en campos finitos de característica pequeña: atacando la criptografía basada en emparejamientos de Tipo 1, Ph.D. thesis, CINVESTAV-IPN, 2016. Available at http://www.cs.cinvestav.mx/TesisGraduados/2016/TesisGoraAdj.pdf.Google Scholar [3] 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, LNCS, 8365 (2014), 20-44. doi: 10.1007/978-3-319-04873-4_2. Google Scholar [4] G. Adj, A. Menezes, T. Oliveira and F. Rodríguez-Henríquez, Weakness of $\mathbb{F}_{3^{6 · 1429}}$    and $\mathbb{F}_{2^{4 · 3041}}$    for discrete logarithm cryptography, Finite Fields and Their Applications, 32 (2015), 148-170. doi: 10.1016/j.ffa.2014.10.009. Google Scholar [5] 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: WAIFI 2014, LNCS, 9061 (2015), 3-22. doi: 10.1007/978-3-319-16277-5_1. Google Scholar [6] R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic: Improvements over FFS in small to medium characteristic, in: Advances in Cryptology - EUROCRYPT 2014, LNCS, 8441 (2014), 1-16. doi: 10.1007/978-3-642-55220-5_1. Google Scholar [7] P. Barreto, S. Galbraith, C. ÓhÉigeartaigh and M. Scott, Efficient pairing computation on supersingular abelian varieties, Designs, Codes and Cryptography, 42 (2007), 239-271. doi: 10.1007/s10623-006-9033-6. Google Scholar [8] P. Barreto, H. Kim, B. Lynn and M. Scott, Efficient algorithms for pairing-based cryptosystems, in: Advances in Cryptology - CRYPTO 2002, LNCS, 2442 (2002), 354-368. doi: 10.1007/3-540-45708-9_23. Google Scholar [9] I. Blake, R. Fuji-Hara, R. Mullin and S. Vanstone, Computing logarithms in finite fields of characteristic two, SIAM Journal on Algebraic and Discrete Methods, 5 (1984), 276-285. doi: 10.1137/0605029. Google Scholar [10] D. Boneh and M. Franklin, Identity-based encryption from the Weil pairing, in: Advances in Cryptology - CRYPTO 2001, LNCS, 2139 (2001), 213-229. doi: 10.1007/3-540-44647-8_13. Google Scholar [11] D. Boneh, B. Lynn and H. Shacham, Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004), 297-319. doi: 10.1007/s00145-004-0314-9. Google Scholar [12] I. Canales-Martínez, Implementación eficiente de prueba de suavidad para polinomios, Tesis de Maestría, CINVESTAV-IPN, 2015. Available at http://delta.cs.cinvestav.mx/~francisco/Thesis_IAC.pdf.Google Scholar [13] D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), 587-594. doi: 10.1109/TIT.1984.1056941. Google Scholar [14] The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/.Google Scholar [15] J. Faugère, A new efficient algorithm for computing Gröbner bases ($F_4$), Journal of Pure and Applied Algebra, 139 (1999), 61-88. doi: 10.1016/S0022-4049(99)00005-5. Google Scholar [16] G. Frey and H. Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of Computation, 62 (1994), 865-874. doi: 10.2307/2153546. Google Scholar [17] S. Galbraith, Supersingular curves in cryptography, in: Advances in Cryptology - ASIACRYPT 2001, LNCS 2248 (2001), 495-513. doi: 10.1007/3-540-45682-1_29. Google Scholar [18] S. Galbraith, K. Harrison and D. Soldera, Implementing the Tate pairing, in: Algorithmic Number Theory - ANTS 2002, LNCS, 2369 (2002), 324-337. doi: 10.1007/3-540-45455-1_26. Google Scholar [19] 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}}$ , in: Advances in Cryptology - CRYPTO 2013, LNCS, 8043 (2013), 109-128. doi: 10.1007/978-3-642-40084-1_7. Google Scholar [20] 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 2014, LNC, S 8282 (2014), 136-152.Google Scholar [21] D. Gordon, Discrete logarithms in $GF(p)$ using the number field sieve, SIAM Journal on Discrete Mathematics, 6 (1993), 124-138. doi: 10.1137/0406010. Google Scholar [22] R. Granger, T. Kleinjung and J. Zumbrägel, Breaking 128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$    and $\mathbb{F}_{2^{12 · 367}}$) , in: Advances in Cryptology - CRYPTO 2014, Part II, LNCS, 8617 (2014), 126-145. doi: 10.1007/978-3-662-44381-1_8. Google Scholar [23] R. Granger, T. Kleinjung and J. Zumbrägel, Breaking '128-bit secure' supersingular binary curves (or how to solve discrete logarithms in $\mathbb{F}_{2^{4 · 1223}}$    and $\mathbb{F}_{2^{12 · 367}}$) , Cryptology ePrint Archive: Report 2014/119, http://eprint.iacr.org/2014/119.Google Scholar [24] R. Granger, T. Kleinjung and J. Zumbrägel, On the discrete logarithm problem in finite fields of fixed characteristic, Transactions of the AMS, 370 (2018), 3129-3145. doi: 10.1090/tran/7027. Google Scholar [25] A. Guillevic, Faster individual discrete logarithms with the QPA and NFS variants, Cryptology ePrint Archive: Report 2016/684, https://eprint.iacr.org/2016/684.Google Scholar [26] A. Joux, A new index calculus algorithm with complexity $L(1/4 + o(1))$ in very small characteristic, in: Selected Areas in Cryptography - SAC 2013, LNCS, 8282 (2014), 355-379. doi: 10.1007/978-3-662-43414-7_18. Google Scholar [27] A. Joux and R. Lercier, The function field sieve in the medium prime case, in: Advances in Cryptology - EUROCRYPT 2006, LNCS, 4004 (2006), 254-270. doi: 10.1007/11761679_16. Google Scholar [28] A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms, in: Advances in Cryptology - ASIACRYPT 2014, LNCS, 8873 (2014), 378-397. doi: 10.1007/978-3-662-45611-8_20. Google Scholar [29] A. Joux and C. Pierrot, Technical history of discrete logarithms in small characteristic finite fields, Designs, Codes and Cryptography, 78 (2016), 73-85. doi: 10.1007/s10623-015-0147-6. Google Scholar [30] A. Knopfmacher and J. Knopfmacher, Counting irreducible factors of polynomials over a finite fields, Discrete Mathematics, 112 (1993), 103-118. doi: 10.1016/0012-365X(93)90227-K. Google Scholar [31] A. Lenstra, Unbelievable security: Matching AES security using public key systems, in: Advances in Cryptology - ASIACRYPT 2001, LNCS, 2248 (2001), 67-86. doi: 10.1007/3-540-45682-1_5. Google Scholar [32] Magma v2.19-7, http://magma.maths.usyd.edu.au/magma/.Google Scholar [33] [34] A. Menezes, T. Okamoto and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, 39 (1993), 1639-1646. doi: 10.1109/18.259647. Google Scholar [35] O. Schirokauer, Discrete logarithms and local units, Philosophical Transactions of the Royal Society London A, 345 (1993), 409-423. doi: 10.1098/rsta.1993.0139. Google Scholar [36] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, 32 (1986), 54-62. doi: 10.1109/TIT.1986.1057137. Google Scholar
CPU times of each stage of the computation of discrete logarithms in $\mathbb{F}_{3^{6 \cdot 509}}$
 Computation stage CPU time (years) CPU frequency (GHz) Finding logarithms of quadratic polynomials Relation generation $0.0003$ 3.20 Linear algebra $0.49$ 2.40 Finding logarithms of cubics Relation generation $0.14$ 3.20 Linear algebra $43.28$ 2.60 Finding logarithms of quartics (29 families) Relation generation $4.01$ 2.60 Linear algebra $94.70$ 2.60 Descent Continued-fractions (508 to 40) $51.00$ 2.87 Classical (40 to 21) $9.85$ 2.66 Classical (21 to 15) $10.10$ 2.66 Small degree (15 to 4) $6.18$ 3.00 Total CPU time (years) $219.75$
 Computation stage CPU time (years) CPU frequency (GHz) Finding logarithms of quadratic polynomials Relation generation $0.0003$ 3.20 Linear algebra $0.49$ 2.40 Finding logarithms of cubics Relation generation $0.14$ 3.20 Linear algebra $43.28$ 2.60 Finding logarithms of quartics (29 families) Relation generation $4.01$ 2.60 Linear algebra $94.70$ 2.60 Descent Continued-fractions (508 to 40) $51.00$ 2.87 Classical (40 to 21) $9.85$ 2.66 Classical (21 to 15) $10.10$ 2.66 Small degree (15 to 4) $6.18$ 3.00 Total CPU time (years) $219.75$
Number of polynomials of each degree in the interval $[5, 15]$ obtained after the continued-fractions and classical descents. The total number of polynomials is 1409
 Degree 5 6 7 8 9 10 11 12 13 14 15 Number of polynomials 101 107 94 98 92 116 137 123 155 173 213
 Degree 5 6 7 8 9 10 11 12 13 14 15 Number of polynomials 101 107 94 98 92 116 137 123 155 173 213
Expected number of irreducible quartics resulting from all the Gröbner bases and zigzag descent steps for each degree in $[5, 15]$
 Degree 5 6 7 8 9 10 11 12 13 14 15 Number of degree-4 polynomials $2^{14.18}$ $2^{14.26}$ $2^{21.27}$ $2^{16.13}$ $2^{22.11}$ $2^{23.88}$ $2^{28.54}$ $2^{23.97}$ $2^{28.74}$ $2^{24.88}$ $2^{30.45}$
 Degree 5 6 7 8 9 10 11 12 13 14 15 Number of degree-4 polynomials $2^{14.18}$ $2^{14.26}$ $2^{21.27}$ $2^{16.13}$ $2^{22.11}$ $2^{23.88}$ $2^{28.54}$ $2^{23.97}$ $2^{28.74}$ $2^{24.88}$ $2^{30.45}$
For every family from $\mathcal{B}_3$, $\mathcal{B}_{4, u^i}$, $i \in [0, 28]$, the inverse of the probability for a random irreducible quartic to descend based on that family
 $\mathcal{B}_3\;\;2^{0.829}$ $\mathcal{B}_{4, u^0}\;\;2^{2.102}$ $\mathcal{B}_{4, u^1}\;\;2^{3.374}$ $\mathcal{B}_{4, u^2}\;\;2^{4.646}$ $\mathcal{B}_{4, u^3}\;\;2^{5.918}$ $\mathcal{B}_{4, u^4}\;\;2^{7.191}$ $\mathcal{B}_{4, u^5}\;\;2^{8.463}$ $\mathcal{B}_{4, u^6}\;\;2^{9.735}$ $\mathcal{B}_{4, u^7}\;\;2^{11.008}$ $\mathcal{B}_{4, u^8}\;\;2^{12.280}$ $\mathcal{B}_{4, u^9}\;\;2^{13.552}$ $\mathcal{B}_{4, u^{10}}\;\;2^{14.825}$ $\mathcal{B}_{4, u^{11}}\;\;2^{16.097}$ $\mathcal{B}_{4, u^{12}}\;\;2^{17.369}$ $\mathcal{B}_{4, u^{13}}\;\;2^{18.641}$ $\mathcal{B}_{4, u^{14}}\;\;2^{19.914}$ $\mathcal{B}_{4, u^{15}}\;\;2^{21.186}$ $\mathcal{B}_{4, u^{16}}\;\;2^{22.458}$ $\mathcal{B}_{4, u^{17}}\;\;2^{23.731}$ $\mathcal{B}_{4, u^{18}}\;\;2^{25.003}$ $\mathcal{B}_{4, u^{19}}\;\;2^{26.275}$ $\mathcal{B}_{4, u^{20}}\;\;2^{27.547}$ $\mathcal{B}_{4, u^{21}}\;\;2^{28.820}$ $\mathcal{B}_{4, u^{22}}\;\;2^{30.092}$ $\mathcal{B}_{4, u^{23}}\;\;2^{31.364}$ $\mathcal{B}_{4, u^{24}}\;\;2^{32.637}$ $\mathcal{B}_{4, u^{25}}\;\;2^{33.909}$ $\mathcal{B}_{4, u^{26}}\;\;2^{35.181}$ $\mathcal{B}_{4, u^{27}}\;\;2^{36.454}$ $\mathcal{B}_{4, u^{28}}\;\;2^{37.726}$
 $\mathcal{B}_3\;\;2^{0.829}$ $\mathcal{B}_{4, u^0}\;\;2^{2.102}$ $\mathcal{B}_{4, u^1}\;\;2^{3.374}$ $\mathcal{B}_{4, u^2}\;\;2^{4.646}$ $\mathcal{B}_{4, u^3}\;\;2^{5.918}$ $\mathcal{B}_{4, u^4}\;\;2^{7.191}$ $\mathcal{B}_{4, u^5}\;\;2^{8.463}$ $\mathcal{B}_{4, u^6}\;\;2^{9.735}$ $\mathcal{B}_{4, u^7}\;\;2^{11.008}$ $\mathcal{B}_{4, u^8}\;\;2^{12.280}$ $\mathcal{B}_{4, u^9}\;\;2^{13.552}$ $\mathcal{B}_{4, u^{10}}\;\;2^{14.825}$ $\mathcal{B}_{4, u^{11}}\;\;2^{16.097}$ $\mathcal{B}_{4, u^{12}}\;\;2^{17.369}$ $\mathcal{B}_{4, u^{13}}\;\;2^{18.641}$ $\mathcal{B}_{4, u^{14}}\;\;2^{19.914}$ $\mathcal{B}_{4, u^{15}}\;\;2^{21.186}$ $\mathcal{B}_{4, u^{16}}\;\;2^{22.458}$ $\mathcal{B}_{4, u^{17}}\;\;2^{23.731}$ $\mathcal{B}_{4, u^{18}}\;\;2^{25.003}$ $\mathcal{B}_{4, u^{19}}\;\;2^{26.275}$ $\mathcal{B}_{4, u^{20}}\;\;2^{27.547}$ $\mathcal{B}_{4, u^{21}}\;\;2^{28.820}$ $\mathcal{B}_{4, u^{22}}\;\;2^{30.092}$ $\mathcal{B}_{4, u^{23}}\;\;2^{31.364}$ $\mathcal{B}_{4, u^{24}}\;\;2^{32.637}$ $\mathcal{B}_{4, u^{25}}\;\;2^{33.909}$ $\mathcal{B}_{4, u^{26}}\;\;2^{35.181}$ $\mathcal{B}_{4, u^{27}}\;\;2^{36.454}$ $\mathcal{B}_{4, u^{28}}\;\;2^{37.726}$
Total and average CPU times in seconds to obtain the logarithms of all the polynomials of degrees in $[5, 15]$ that resulted from the continued-fractions and classical descents. The times assume that an Intel Xeon E5-2658 v2 2.40 GHz machine with 256 gigabytes of RAM is used
 Degree 5 6 7 8 9 10 11 12 13 14 15 Total $2^{10.21}$ $2^{10.29}$ $2^{17.30}$ $2^{12.16}$ $2^{18.14}$ $2^{19.92}$ $2^{24.57}$ $2^{20.00}$ $2^{24.78}$ $2^{20.91}$ $2^{26.48}$ Average $2^{3.55}$ $2^{3.55}$ $2^{10.69}$ $2^{5.64}$ $2^{11.62}$ $2^{13.06}$ $2^{17.47}$ $2^{13.06}$ $2^{17.50}$ $2^{13.48}$ $2^{18.75}$
 Degree 5 6 7 8 9 10 11 12 13 14 15 Total $2^{10.21}$ $2^{10.29}$ $2^{17.30}$ $2^{12.16}$ $2^{18.14}$ $2^{19.92}$ $2^{24.57}$ $2^{20.00}$ $2^{24.78}$ $2^{20.91}$ $2^{26.48}$ Average $2^{3.55}$ $2^{3.55}$ $2^{10.69}$ $2^{5.64}$ $2^{11.62}$ $2^{13.06}$ $2^{17.47}$ $2^{13.06}$ $2^{17.50}$ $2^{13.48}$ $2^{18.75}$
Estimated costs of the main steps for computing discrete logarithms in $\mathbb{F}_{3^{6.1429}}$
 Finding logarithms of polynomials of degree $\leq 4$ Degrees 1 and 2 $2^{50.7} M_q$ Degree 3 $2^{56.9} M_q$ Degree 4 (36 families) $2^{56.3} M_q$ Descent Guillevic (1428 to 71) $2^{62.4} M_q$ Classical (71 to 32) $2^{61.8} M_q$ Classical (31 to $\{1, \ldots, 16, 18, 20, 22, 24, 28, 32\}$) $2^{59.2}M_q$ Small degree ($\{5, \ldots, 16, 18, 20, 22, 24, 28, 32\}$ to 4) $2^{60.0}M_q$ Total cost $2^{63.4} M_q$
 Finding logarithms of polynomials of degree $\leq 4$ Degrees 1 and 2 $2^{50.7} M_q$ Degree 3 $2^{56.9} M_q$ Degree 4 (36 families) $2^{56.3} M_q$ Descent Guillevic (1428 to 71) $2^{62.4} M_q$ Classical (71 to 32) $2^{61.8} M_q$ Classical (31 to $\{1, \ldots, 16, 18, 20, 22, 24, 28, 32\}$) $2^{59.2}M_q$ Small degree ($\{5, \ldots, 16, 18, 20, 22, 24, 28, 32\}$ to 4) $2^{60.0}M_q$ Total cost $2^{63.4} M_q$
$M_q$ costs of performing all the $D$-to-4 descents for each $D \in S$
 $D$ 5 6 7 8 9 10 11 12 13 $e_D$ 73 68 65 63 63 63 64 65 67 $\log_2(\mbox{cost})$ 36.7 36.6 43.7 38.6 44.6 46 50.5 46.1 50.6 $D$ 14 15 16 18 20 22 24 28 32 $e_D$ 69 72 75 83 92 103 117 151 200 $\log_2(\mbox{cost})$ 46.6 51.9 48.4 54.5 56.1 56.4 56.4 57.2 59.3
 $D$ 5 6 7 8 9 10 11 12 13 $e_D$ 73 68 65 63 63 63 64 65 67 $\log_2(\mbox{cost})$ 36.7 36.6 43.7 38.6 44.6 46 50.5 46.1 50.6 $D$ 14 15 16 18 20 22 24 28 32 $e_D$ 69 72 75 83 92 103 117 151 200 $\log_2(\mbox{cost})$ 46.6 51.9 48.4 54.5 56.1 56.4 56.4 57.2 59.3
Estimated calendar time for computing a discrete logarithm in $\mathbb{F}_{3^{6.1429}}$ using machines ${\mathcal{A}}$ and ${\mathcal{B}}$
 Computation # cores # days Degree-3 logarithms 5824 2 Degree-4 logarithms 9000 1 Guillevic descent 9000 59 First classical descent 9000 39 Second classical descent 9000 7 Small degree descent 1500 65 Total time 173
 Computation # cores # days Degree-3 logarithms 5824 2 Degree-4 logarithms 9000 1 Guillevic descent 9000 59 First classical descent 9000 39 Second classical descent 9000 7 Small degree descent 1500 65 Total time 173

2018 Impact Factor: 0.879