• Previous Article
    A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane
  • AMC Home
  • This Issue
  • Next Article
    New non-binary quantum codes from constacyclic codes over $ \mathbb{F}_q[u,v]/\langle u^{2}-1, v^{2}-v, uv-vu\rangle $
August  2019, 13(3): 435-455. doi: 10.3934/amc.2019028

A unified polynomial selection method for the (tower) number field sieve algorithm

1. 

Indian Statistical Institute, Kolkata 700108, West Bengal, India

2. 

Indian Institute of Science Education and Research Bhopal, Bhopal 462066, Madhya Pradesh, India

* Corresponding author: Shashank Singh

Received  July 2018 Revised  January 2019 Published  April 2019

At Eurocrypt 2015, Barbulescu et al. introduced two new methods of polynomial selection, namely the Conjugation and the Generalised Joux-Lercier methods, for the number field sieve (NFS) algorithm as applied to the discrete logarithm problem over finite fields. A sequence of subsequent works have developed and applied these methods to the multiple and the (extended) tower number field sieve algorithms. This line of work has led to new asymptotic complexities for various cases of the discrete logarithm problem over finite fields. The current work presents a unified polynomial selection method which we call Algorithm $ \mathcal{D} $. Starting from the Barbulescu et al. paper, all the subsequent polynomial selection methods can be seen as special cases of Algorithm $ \mathcal{D} $. Moreover, for the extended tower number field sieve (exTNFS) and the multiple extended TNFS (MexTNFS), there are finite fields for which using the polynomials selected by Algorithm $ \mathcal{D} $ provides the best asymptotic complexity. Suppose $ Q = p^n $ for a prime $ p $ and further suppose that $ n = \eta\kappa $ such that there is a $ c_{\theta}>0 $ for which $ p^{\eta} = L_Q(2/3, c_{\theta}) $. For $ c_{\theta}>3.39 $, the complexity of exTNFS-$ \mathcal{D} $ is lower than the complexities of all previous algorithms; for $ c_{\theta}\notin (0, 1.12)\cup[1.45, 3.15] $, the complexity of MexTNFS-$ \mathcal{D} $ is lower than that of all previous methods.

Citation: 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
References:
[1]

L. M. Adleman, The function field sieve, In Leonard M. Adleman and Ming-Deh A. Huang, editors, ANTS, volume 877 of Lecture Notes in Computer Science, pages 108–121. Springer, 1994. doi: 10.1007/3-540-58691-1_48.  Google Scholar

[2]

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

[3]

R. Barbulescu and S. Duquesne, Updating key size estimations for pairings, Journal of Cryptology, 2018, 1–39. https://link.springer.com/article/10.1007/s00145-018-9280-5. doi: 10.1007/s00145-018-9280-5.  Google Scholar

[4]

R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pages 129–155. Springer Berlin Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_6.  Google Scholar

[5]

R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 1–16. Springer, 2014. doi: 10.1007/978-3-642-55220-5_1.  Google Scholar

[6]

R. Barbulescu, P. Gaudry and T. Kleinjung, The tower number field sieve, In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 31–55. Springer, 2015. doi: 10.1007/978-3-662-48800-3_2.  Google Scholar

[7]

R. Barbulescu and C. Pierrot, The multiple number field sieve for medium and high characteristic finite fields, LMS Journal of Computation and Mathematics, 17 (2014), 230-246.  doi: 10.1112/S1461157014000369.  Google Scholar

[8]

Y. Bistritz and A. Lifshitz, Bounds for resultants of univariate and bivariate polynomials, Linear Algebra and its Applications, 432 (2010), 1995–2005. Special issue devoted to the 15th ILAS Conference at Cancun, Mexico, June 16-20, 2008. doi: 10.1016/j.laa.2009.08.012.  Google Scholar

[9]

N. Gama and P. Q. Nguyen, Predicting lattice reduction, In Nigel Smart, editor, Advances in Cryptology – EUROCRYPT 2008, 31–51, Lecture Notes in Comput. Sci., 4965, Springer, Berlin, 2008. doi: 10.1007/978-3-540-78967-3_3.  Google Scholar

[10]

P. GaudryL. Grémy and M. Videau, Collecting relations for the number field sieve in GF(p6), LMS Journal of Computation and Mathematics, 19 (2016), 332-350.  doi: 10.1112/S1461157016000164.  Google Scholar

[11]

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

[12]

R. Granger, T. Kleinjung and J. Zumbrägel, Discrete logarithms in GF(29234), NMBRTHRY list, January 2014. Google Scholar

[13]

A. Guillevic, Computing individual discrete logarithms faster in GF(pn) with the NFS-DL algorithm, Advances in cryptology–ASIACRYPT 2015. Part I, 149–173, Lecture Notes in Comput. Sci., 9452, Springer, Heidelberg, 2015, http://eprint.iacr.org/. doi: 10.1007/978-3-662-48797-6_7.  Google Scholar

[14]

A. Guillevic, F. Morain and E. Thomé, Solving discrete logarithms on a 170-bit MNT curve by pairing reduction, Selected Areas in Cryptography – SAC 2016, 2017,559–578. http://eprint.iacr.org/. doi: 10.1007/978-3-319-69453-5_30.  Google Scholar

[15]

K. HayasakaK. AokiT. Kobayashi and T. Takagi, A construction of 3-dimensional lattice sieve for number field sieve over $ \mathbb{F}_{p^n} $, JSIAM Lett., 6 (2014), 53-56.  doi: 10.14495/jsiaml.6.53.  Google Scholar

[16]

A. Joux, Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields, In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 177–193. Springer, 2013. doi: 10.1007/978-3-642-38348-9_11.  Google Scholar

[17]

A. Joux, A new index calculus algorithm with complexity $ L(1/4+o(1)) $ in small characteristic, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, pages 355–379. Springer, 2014. doi: 10.1007/978-3-662-43414-7_18.  Google Scholar

[18]

A. Joux and R. Lercier, The function field sieve is quite special, In Claus Fieker and David R. Kohel, editors, ANTS, volume 2369 of Lecture Notes in Computer Science, pages 431–445. Springer, 2002. doi: 10.1007/3-540-45455-1_34.  Google Scholar

[19]

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

[20]

A. Joux and R. Lercier, The function field sieve in the medium prime case, In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 254–270. Springer, 2006. doi: 10.1007/11761679_16.  Google Scholar

[21]

A. Joux, R. Lercier, N. P. Smart and F. Vercauteren, The number field sieve in the medium prime case, In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture Notes in Computer Science, pages 326–344. Springer Berlin Heidelberg, 2006. doi: 10.1007/11818175_19.  Google Scholar

[22]

A. Joux and C. Pierrot, The special number field sieve in $ \mathbb{F}_{p^n} $ - Application to pairing-friendly constructions, In Zhenfu Cao and Fangguo Zhang, editors, Pairing-Based Cryptography - Pairing 2013 - 6th International Conference, Beijing, China, November 22-24, 2013, Revised Selected Papers, volume 8365 of Lecture Notes in Computer Science, pages 45–61. Springer, 2013. doi: 10.1007/978-3-319-04873-4_3.  Google Scholar

[23]

A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms - simplified setting for small characteristic finite fields, In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, pages 378–397. Springer, 2014. doi: 10.1007/978-3-662-45611-8_20.  Google Scholar

[24]

T. Kim and R. Barbulescu, Extended tower number field sieve: A new complexity for the medium prime case, In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 543–571. Springer, 2016. doi: 10.1007/978-3-662-53018-4_20.  Google Scholar

[25]

T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, In Serge Fehr, editor, Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I, volume 10174 of Lecture Notes in Computer Science, pages 388–408. Springer, 2017.  Google Scholar

[26]

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

[27]

A. Menezes, P. Sarkar and S. Singh, Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography, In Mycrypt, volume 10311 of Lecture Notes in Computer Science, pages 83–108. Springer, 2016. doi: 10.1007/978-3-319-61273-7_5.  Google Scholar

[28]

C. Pierrot, The multiple number field sieve with conjugation and generalized Joux-Lercier methods, In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 156–170, Lecture Notes in Comput. Sci., 9056, Springer, Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_7.  Google Scholar

[29]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory, 62 (2016), 2233–2253. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=7405328. doi: 10.1109/TIT.2016.2528996.  Google Scholar

[30]

P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 37–62, 2016. doi: 10.1007/978-3-662-53887-6_2.  Google Scholar

[31]

P. Sarkar and S. Singh, New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields, In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 429–458, Springer, 2016. doi: 10.1007/978-3-662-49890-3_17.  Google Scholar

[32]

O. Schirokauer, Discrete logarithms and local units, Philosophical Transactions: Physical Sciences and Engineering, 345 91993), 409–423. doi: 10.1098/rsta.1993.0139.  Google Scholar

[33]

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

[34]

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

[35]

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

[36]

P. Zajac, On the use of the lattice sieve in the 3d NFS, Tatra Mountains Mathematical Publications, 45 (2010), 161-172.  doi: 10.2478/v10127-010-0012-y.  Google Scholar

show all references

References:
[1]

L. M. Adleman, The function field sieve, In Leonard M. Adleman and Ming-Deh A. Huang, editors, ANTS, volume 877 of Lecture Notes in Computer Science, pages 108–121. Springer, 1994. doi: 10.1007/3-540-58691-1_48.  Google Scholar

[2]

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

[3]

R. Barbulescu and S. Duquesne, Updating key size estimations for pairings, Journal of Cryptology, 2018, 1–39. https://link.springer.com/article/10.1007/s00145-018-9280-5. doi: 10.1007/s00145-018-9280-5.  Google Scholar

[4]

R. Barbulescu, P. Gaudry, A. Guillevic and F. Morain, Improving NFS for the discrete logarithm problem in non-prime finite fields, In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, volume 9056 of Lecture Notes in Computer Science, pages 129–155. Springer Berlin Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_6.  Google Scholar

[5]

R. Barbulescu, P. Gaudry, A. Joux and E. Thomé, A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 1–16. Springer, 2014. doi: 10.1007/978-3-642-55220-5_1.  Google Scholar

[6]

R. Barbulescu, P. Gaudry and T. Kleinjung, The tower number field sieve, In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 31–55. Springer, 2015. doi: 10.1007/978-3-662-48800-3_2.  Google Scholar

[7]

R. Barbulescu and C. Pierrot, The multiple number field sieve for medium and high characteristic finite fields, LMS Journal of Computation and Mathematics, 17 (2014), 230-246.  doi: 10.1112/S1461157014000369.  Google Scholar

[8]

Y. Bistritz and A. Lifshitz, Bounds for resultants of univariate and bivariate polynomials, Linear Algebra and its Applications, 432 (2010), 1995–2005. Special issue devoted to the 15th ILAS Conference at Cancun, Mexico, June 16-20, 2008. doi: 10.1016/j.laa.2009.08.012.  Google Scholar

[9]

N. Gama and P. Q. Nguyen, Predicting lattice reduction, In Nigel Smart, editor, Advances in Cryptology – EUROCRYPT 2008, 31–51, Lecture Notes in Comput. Sci., 4965, Springer, Berlin, 2008. doi: 10.1007/978-3-540-78967-3_3.  Google Scholar

[10]

P. GaudryL. Grémy and M. Videau, Collecting relations for the number field sieve in GF(p6), LMS Journal of Computation and Mathematics, 19 (2016), 332-350.  doi: 10.1112/S1461157016000164.  Google Scholar

[11]

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

[12]

R. Granger, T. Kleinjung and J. Zumbrägel, Discrete logarithms in GF(29234), NMBRTHRY list, January 2014. Google Scholar

[13]

A. Guillevic, Computing individual discrete logarithms faster in GF(pn) with the NFS-DL algorithm, Advances in cryptology–ASIACRYPT 2015. Part I, 149–173, Lecture Notes in Comput. Sci., 9452, Springer, Heidelberg, 2015, http://eprint.iacr.org/. doi: 10.1007/978-3-662-48797-6_7.  Google Scholar

[14]

A. Guillevic, F. Morain and E. Thomé, Solving discrete logarithms on a 170-bit MNT curve by pairing reduction, Selected Areas in Cryptography – SAC 2016, 2017,559–578. http://eprint.iacr.org/. doi: 10.1007/978-3-319-69453-5_30.  Google Scholar

[15]

K. HayasakaK. AokiT. Kobayashi and T. Takagi, A construction of 3-dimensional lattice sieve for number field sieve over $ \mathbb{F}_{p^n} $, JSIAM Lett., 6 (2014), 53-56.  doi: 10.14495/jsiaml.6.53.  Google Scholar

[16]

A. Joux, Faster index calculus for the medium prime case: Application to 1175-bit and 1425-bit finite fields, In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 177–193. Springer, 2013. doi: 10.1007/978-3-642-38348-9_11.  Google Scholar

[17]

A. Joux, A new index calculus algorithm with complexity $ L(1/4+o(1)) $ in small characteristic, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, pages 355–379. Springer, 2014. doi: 10.1007/978-3-662-43414-7_18.  Google Scholar

[18]

A. Joux and R. Lercier, The function field sieve is quite special, In Claus Fieker and David R. Kohel, editors, ANTS, volume 2369 of Lecture Notes in Computer Science, pages 431–445. Springer, 2002. doi: 10.1007/3-540-45455-1_34.  Google Scholar

[19]

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

[20]

A. Joux and R. Lercier, The function field sieve in the medium prime case, In Serge Vaudenay, editor, EUROCRYPT, volume 4004 of Lecture Notes in Computer Science, pages 254–270. Springer, 2006. doi: 10.1007/11761679_16.  Google Scholar

[21]

A. Joux, R. Lercier, N. P. Smart and F. Vercauteren, The number field sieve in the medium prime case, In Cynthia Dwork, editor, Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, volume 4117 of Lecture Notes in Computer Science, pages 326–344. Springer Berlin Heidelberg, 2006. doi: 10.1007/11818175_19.  Google Scholar

[22]

A. Joux and C. Pierrot, The special number field sieve in $ \mathbb{F}_{p^n} $ - Application to pairing-friendly constructions, In Zhenfu Cao and Fangguo Zhang, editors, Pairing-Based Cryptography - Pairing 2013 - 6th International Conference, Beijing, China, November 22-24, 2013, Revised Selected Papers, volume 8365 of Lecture Notes in Computer Science, pages 45–61. Springer, 2013. doi: 10.1007/978-3-319-04873-4_3.  Google Scholar

[23]

A. Joux and C. Pierrot, Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms - simplified setting for small characteristic finite fields, In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, volume 8873 of Lecture Notes in Computer Science, pages 378–397. Springer, 2014. doi: 10.1007/978-3-662-45611-8_20.  Google Scholar

[24]

T. Kim and R. Barbulescu, Extended tower number field sieve: A new complexity for the medium prime case, In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 543–571. Springer, 2016. doi: 10.1007/978-3-662-53018-4_20.  Google Scholar

[25]

T. Kim and J. Jeong, Extended tower number field sieve with application to finite fields of arbitrary composite extension degree, In Serge Fehr, editor, Public-Key Cryptography - PKC 2017 - 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands, March 28-31, 2017, Proceedings, Part I, volume 10174 of Lecture Notes in Computer Science, pages 388–408. Springer, 2017.  Google Scholar

[26]

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

[27]

A. Menezes, P. Sarkar and S. Singh, Challenges with assessing the impact of NFS advances on the security of pairing-based cryptography, In Mycrypt, volume 10311 of Lecture Notes in Computer Science, pages 83–108. Springer, 2016. doi: 10.1007/978-3-319-61273-7_5.  Google Scholar

[28]

C. Pierrot, The multiple number field sieve with conjugation and generalized Joux-Lercier methods, In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, pages 156–170, Lecture Notes in Comput. Sci., 9056, Springer, Heidelberg, 2015. doi: 10.1007/978-3-662-46800-5_7.  Google Scholar

[29]

P. Sarkar and S. Singh, Fine tuning the function field sieve algorithm for the medium prime case, IEEE Transactions on Information Theory, 62 (2016), 2233–2253. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&arnumber=7405328. doi: 10.1109/TIT.2016.2528996.  Google Scholar

[30]

P. Sarkar and S. Singh, A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm, In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 37–62, 2016. doi: 10.1007/978-3-662-53887-6_2.  Google Scholar

[31]

P. Sarkar and S. Singh, New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields, In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 429–458, Springer, 2016. doi: 10.1007/978-3-662-49890-3_17.  Google Scholar

[32]

O. Schirokauer, Discrete logarithms and local units, Philosophical Transactions: Physical Sciences and Engineering, 345 91993), 409–423. doi: 10.1098/rsta.1993.0139.  Google Scholar

[33]

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

[34]

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

[35]

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

[36]

P. Zajac, On the use of the lattice sieve in the 3d NFS, Tatra Mountains Mathematical Publications, 45 (2010), 161-172.  doi: 10.2478/v10127-010-0012-y.  Google Scholar

Figure 1.  Tower of Number Fields
Figure 2.  Commutative diagram for TNFS
Figure 3.  Product of norms for various polynomial selection methods
Figure 4.  Complexity plot for medium characteristic finite fields
Figure 5.  Complexity plot for medium characteristic finite fields
Table 1.  Parameterised efficiency estimates for NFS obtained from the different polynomial selection methods
Method Norms Product Conditions
NFS-JLSV1[21] $E^{\frac{4n}{t}}Q^{\frac{t-1}{n}}$
NFS-GJL[4] $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $r\geq n$
NFS-Conj[4] $E^{\frac{6n}{t}}Q^{\frac{t-1}{2n}}$
NFS-$\mathcal{A}$[31] $E^{\frac{2d(2r+1)}{t}}Q^{\frac{t-1}{d(r+1)}}$ $d|n$, $r\geq n/d$
exTNFS-JLSV1[24] $E^{\frac{4\kappa}{t}}Q^{\frac{t-1}{\kappa}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$
exTNFS-GJL[24] $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$, $r\geq\kappa$
exTNFS-$\mathcal{C}$[30] $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)(r(\lambda-1)+k)}{\kappa(r\lambda+1)}}$ $n=\eta\kappa$, $k=\kappa/d$, $r\geq k$, $\lambda\in\{1, \eta\}$
exTNFS-gConj [25] $E^{\frac{6\kappa}{t}}Q^{\frac{t-1}{2\kappa}}$ $n=\eta\kappa$
exTNFS-$\mathcal{D}$ $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)}{d(r+1)}}$ $n=\eta\kappa$, $d|\kappa$, $\gcd(\eta, \kappa/d)=1$, $r\geq \kappa/d$
NFS-GJL:$\eta=d=1$
NFS-Conj:$\eta=1$, $d=\kappa=n$, $r=1$
NFS-$\mathcal{A}$:$\eta=1$, $\kappa=n$, $d|n$, $r\geq n/d$
exTNFS-GJL:$d=1$
exTNFS-gConj:$d=\kappa$, $r=1$
Method Norms Product Conditions
NFS-JLSV1[21] $E^{\frac{4n}{t}}Q^{\frac{t-1}{n}}$
NFS-GJL[4] $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $r\geq n$
NFS-Conj[4] $E^{\frac{6n}{t}}Q^{\frac{t-1}{2n}}$
NFS-$\mathcal{A}$[31] $E^{\frac{2d(2r+1)}{t}}Q^{\frac{t-1}{d(r+1)}}$ $d|n$, $r\geq n/d$
exTNFS-JLSV1[24] $E^{\frac{4\kappa}{t}}Q^{\frac{t-1}{\kappa}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$
exTNFS-GJL[24] $E^{\frac{2(2r+1)}{t}}Q^{\frac{t-1}{r+1}}$ $n=\eta\kappa$, $\gcd(\eta, \kappa)=1$, $r\geq\kappa$
exTNFS-$\mathcal{C}$[30] $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)(r(\lambda-1)+k)}{\kappa(r\lambda+1)}}$ $n=\eta\kappa$, $k=\kappa/d$, $r\geq k$, $\lambda\in\{1, \eta\}$
exTNFS-gConj [25] $E^{\frac{6\kappa}{t}}Q^{\frac{t-1}{2\kappa}}$ $n=\eta\kappa$
exTNFS-$\mathcal{D}$ $E^{\frac{2d(2r+1)}{t}}Q^{\frac{(t-1)}{d(r+1)}}$ $n=\eta\kappa$, $d|\kappa$, $\gcd(\eta, \kappa/d)=1$, $r\geq \kappa/d$
NFS-GJL:$\eta=d=1$
NFS-Conj:$\eta=1$, $d=\kappa=n$, $r=1$
NFS-$\mathcal{A}$:$\eta=1$, $\kappa=n$, $d|n$, $r\geq n/d$
exTNFS-GJL:$d=1$
exTNFS-gConj:$d=\kappa$, $r=1$
[1]

Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020119

[2]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

[3]

Laura Aquilanti, Simone Cacace, Fabio Camilli, Raul De Maio. A Mean Field Games model for finite mixtures of Bernoulli and categorical distributions. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2020033

[4]

Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016

[5]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089

[6]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127

[7]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[8]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

[9]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[10]

Illés Horváth, Kristóf Attila Horváth, Péter Kovács, Miklós Telek. Mean-field analysis of a scaling MAC radio protocol. Journal of Industrial & Management Optimization, 2021, 17 (1) : 279-297. doi: 10.3934/jimo.2019111

[11]

Josselin Garnier, Knut Sølna. Enhanced Backscattering of a partially coherent field from an anisotropic random lossy medium. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1171-1195. doi: 10.3934/dcdsb.2020158

[12]

Jann-Long Chern, Sze-Guang Yang, Zhi-You Chen, Chih-Her Chen. On the family of non-topological solutions for the elliptic system arising from a product Abelian gauge field theory. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3291-3304. doi: 10.3934/dcds.2020127

[13]

Daniele Bartolucci, Changfeng Gui, Yeyao Hu, Aleks Jevnikar, Wen Yang. Mean field equations on tori: Existence and uniqueness of evenly symmetric blow-up solutions. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3093-3116. doi: 10.3934/dcds.2020039

[14]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[15]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[16]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[17]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[18]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226

[19]

Xiaoli Lu, Pengzhan Huang, Yinnian He. Fully discrete finite element approximation of the 2D/3D unsteady incompressible magnetohydrodynamic-Voigt regularization flows. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 815-845. doi: 10.3934/dcdsb.2020143

[20]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (271)
  • HTML views (539)
  • Cited by (1)

Other articles
by authors

[Back to Top]