• Previous 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 $
  • AMC Home
  • This Issue
  • Next Article
    A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane
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.

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

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

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

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

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

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

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

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

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

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

[12]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[32]

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

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

[34]

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

[12]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[32]

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

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

[34]

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

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

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

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]

Francesco Cellarosi, Ilya Vinogradov. Ergodic properties of $k$-free integers in number fields. Journal of Modern Dynamics, 2013, 7 (3) : 461-488. doi: 10.3934/jmd.2013.7.461

[2]

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

[3]

Qixuan Wang, Hans G. Othmer. The performance of discrete models of low reynolds number swimmers. Mathematical Biosciences & Engineering, 2015, 12 (6) : 1303-1320. doi: 10.3934/mbe.2015.12.1303

[4]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[5]

Jean-François Biasse. Subexponential time relations in the class group of large degree number fields. Advances in Mathematics of Communications, 2014, 8 (4) : 407-425. doi: 10.3934/amc.2014.8.407

[6]

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

[7]

Xiaolu Hou, Frédérique Oggier. Modular lattices from a variation of construction a over number fields. Advances in Mathematics of Communications, 2017, 11 (4) : 719-745. doi: 10.3934/amc.2017053

[8]

Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465

[9]

Hui Cao, Yicang Zhou. The basic reproduction number of discrete SIR and SEIS models with periodic parameters. Discrete & Continuous Dynamical Systems - B, 2013, 18 (1) : 37-56. doi: 10.3934/dcdsb.2013.18.37

[10]

Harald Fripertinger. The number of invariant subspaces under a linear operator on finite vector spaces. Advances in Mathematics of Communications, 2011, 5 (2) : 407-416. doi: 10.3934/amc.2011.5.407

[11]

Timothy C. Reluga, Jan Medlock, Alison Galvani. The discounted reproductive number for epidemiology. Mathematical Biosciences & Engineering, 2009, 6 (2) : 377-393. doi: 10.3934/mbe.2009.6.377

[12]

Michel Laurent, Arnaldo Nogueira. Rotation number of contracted rotations. Journal of Modern Dynamics, 2018, 12: 175-191. doi: 10.3934/jmd.2018007

[13]

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

[14]

Thomas Alazard. A minicourse on the low Mach number limit. Discrete & Continuous Dynamical Systems - S, 2008, 1 (3) : 365-404. doi: 10.3934/dcdss.2008.1.365

[15]

Wilfrid Gangbo, Andrzej Świech. Optimal transport and large number of particles. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1397-1441. doi: 10.3934/dcds.2014.34.1397

[16]

Sujay Jayakar, Robert S. Strichartz. Average number of lattice points in a disk. Communications on Pure & Applied Analysis, 2016, 15 (1) : 1-8. doi: 10.3934/cpaa.2016.15.1

[17]

G.F. Webb. The prime number periodical cicada problem. Discrete & Continuous Dynamical Systems - B, 2001, 1 (3) : 387-399. doi: 10.3934/dcdsb.2001.1.387

[18]

Tiago de Carvalho, Bruno Freitas. Birth of an arbitrary number of T-singularities in 3D piecewise smooth vector fields. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 1-11. doi: 10.3934/dcdsb.2019034

[19]

Noureddine Jilani Ben Naouara, Faouzi Trabelsi. Generalization on optimal multiple stopping with application to swing options with random exercise rights number. Mathematical Control & Related Fields, 2015, 5 (4) : 807-826. doi: 10.3934/mcrf.2015.5.807

[20]

Ata Allah Taleizadeh, Solaleh Sadat Kalantari, Leopoldo Eduardo Cárdenas-Barrón. Determining optimal price, replenishment lot size and number of shipments for an EPQ model with rework and multiple shipments. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1059-1071. doi: 10.3934/jimo.2015.11.1059

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (47)
  • HTML views (273)
  • Cited by (0)

Other articles
by authors

[Back to Top]