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

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

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

[4]

G. AdjA. MenezesT. 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.

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

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

[7]

P. BarretoS. GalbraithC. Ó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.

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

[9]

I. BlakeR. Fuji-HaraR. 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.

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

[11]

D. BonehB. Lynn and H. Shacham, Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004), 297-319. doi: 10.1007/s00145-004-0314-9.

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

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

[14]

The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/.

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

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

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

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

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

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

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

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

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

[24]

R. GrangerT. 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.

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

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

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

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

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

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

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

[32]

Magma v2.19-7, http://magma.maths.usyd.edu.au/magma/.

[33]

Maple 2016, http://www.maplesoft.com/products/maple/.

[34]

A. MenezesT. 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.

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

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

show all references

References:
[1]

ABACUS Supercomputer - Cinvestav, http://www.abacus.cinvestav.mx/.

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

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

[4]

G. AdjA. MenezesT. 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.

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

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

[7]

P. BarretoS. GalbraithC. Ó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.

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

[9]

I. BlakeR. Fuji-HaraR. 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.

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

[11]

D. BonehB. Lynn and H. Shacham, Short signatures from the Weil pairing, Journal of Cryptology, 17 (2004), 297-319. doi: 10.1007/s00145-004-0314-9.

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

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

[14]

The Cunningham Project, http://homes.cerias.purdue.edu/~ssw/cun/.

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

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

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

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

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

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

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

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

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

[24]

R. GrangerT. 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.

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

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

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

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

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

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

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

[32]

Magma v2.19-7, http://magma.maths.usyd.edu.au/magma/.

[33]

Maple 2016, http://www.maplesoft.com/products/maple/.

[34]

A. MenezesT. 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.

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

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

Table 1.  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$
Table 4.  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
Table 2.  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}$
Table 3.  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}$
Table 5.  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}$
Table 6.  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$
Table 7.  $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.0 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.0 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
Table 8.  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
[1]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281

[2]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489

[3]

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

[4]

Lars Eirik Danielsen. Graph-based classification of self-dual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329-348. doi: 10.3934/amc.2009.3.329

[5]

Rafael Ayala, Jose Antonio Vilches, Gregor Jerše, Neža Mramor Kosta. Discrete gradient fields on infinite complexes. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 623-639. doi: 10.3934/dcds.2011.30.623

[6]

Yong Zhang, Huifen Zhong, Yue Liu, Menghu Huang. Online ordering strategy for the discrete newsvendor problem with order value-based free-shipping. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018114

[7]

Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-25. doi: 10.3934/dcdsb.2018235

[8]

Indranil Biswas, Georg Schumacher, Lin Weng. Deligne pairing and determinant bundle. Electronic Research Announcements, 2011, 18: 91-96. doi: 10.3934/era.2011.18.91

[9]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107

[10]

Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901

[11]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459

[12]

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

[13]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203

[14]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022

[15]

Yingwen Guo, Yinnian He. Fully discrete finite element method based on second-order Crank-Nicolson/Adams-Bashforth scheme for the equations of motion of Oldroyd fluids of order one. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2583-2609. doi: 10.3934/dcdsb.2015.20.2583

[16]

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101

[17]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475

[18]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1

[19]

Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321

[20]

Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63

[Back to Top]