{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:51:46Z","timestamp":1780051906481,"version":"3.53.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T00:00:00Z","timestamp":1771200000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2024JBZY011"],"award-info":[{"award-number":["2024JBZY011"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62002015"],"award-info":[{"award-number":["62002015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701552"],"award-info":[{"award-number":["11701552"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s10623-025-01788-5","type":"journal-article","created":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T06:54:45Z","timestamp":1771224885000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the complexity formulae of the number field sieve and its variants"],"prefix":"10.1007","volume":"94","author":[{"given":"Yuqing","family":"Zhu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chang","family":"Lv","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiqiang","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,2,16]]},"reference":[{"key":"1788_CR1","unstructured":"Bai, S.: Polynomial selection for the number field sieve. Ph.D. thesis, Australian National University, Canberra (2011)"},{"issue":"298","key":"1788_CR2","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1090\/mcom3048","volume":"85","author":"S Bai","year":"2016","unstructured":"Bai S., Bouvier C., Kruppa A., Zimmermann P.: Better polynomials for GNFS. Math. Comput. 85(298), 861\u2013873 (2016).","journal-title":"Math. Comput."},{"key":"1788_CR3","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1007\/s00145-018-9280-5","volume":"32","author":"R Barbulescu","year":"2019","unstructured":"Barbulescu R., Duquesne S.: Updating key size estimations for pairings. J. Cryptol. 32, 1298\u20131336 (2019).","journal-title":"J. Cryptol."},{"key":"1788_CR4","doi-asserted-by":"crossref","unstructured":"Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F.: Improving NFS for the discrete logarithm problem in non-prime finite fields. In: Advances in Cryptology \u2013 EUROCRYPT 2015. pp. 129\u2013155. Springer (2015)","DOI":"10.1007\/978-3-662-46800-5_6"},{"key":"1788_CR5","doi-asserted-by":"crossref","unstructured":"Barbulescu, R., Gaudry, P., Joux, A., Thom\u00e9, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Advances in Cryptology - EUROCRYPT 2014. pp. 1\u201316 (2014)","DOI":"10.1007\/978-3-642-55220-5_1"},{"key":"1788_CR6","doi-asserted-by":"crossref","unstructured":"Barbulescu, R., Gaudry, P., Kleinjung, T.: The tower number field sieve. In: Advances in Cryptology \u2013 ASIACRYPT 2015. pp. 31\u201355. Springer (2015)","DOI":"10.1007\/978-3-662-48800-3_2"},{"issue":"A","key":"1788_CR7","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1112\/S1461157014000369","volume":"17","author":"R Barbulescu","year":"2014","unstructured":"Barbulescu R., Pierrot C.: The multiple number field sieve for medium-and high-characteristic finite fields. LMS J. Comput. Math. 17(A), 230\u2013246 (2014).","journal-title":"LMS J. Comput. Math."},{"key":"1788_CR8","doi-asserted-by":"crossref","unstructured":"Buhler, J.P., Lenstra, H.W., Pomerance, C.: Factoring integers with the number field sieve. In: The development of the number field sieve, pp. 50\u201394. Springer (1993)","DOI":"10.1007\/BFb0091539"},{"issue":"1","key":"1788_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0022-314X(83)90002-1","volume":"17","author":"ER Canfield","year":"1983","unstructured":"Canfield E.R., Erd\u00f6s P., Pomerance C.: On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u2019\u2019. Journal of Number Theory 17(1), 1\u201328 (1983).","journal-title":"Journal of Number Theory"},{"key":"1788_CR10","doi-asserted-by":"crossref","unstructured":"Commeine, A., Semaev, I.: An algorithm to solve the discrete logarithm problem with the number field sieve. In: Public Key Cryptography \u2013 PKC 2006. pp. 174\u2013190. Springer (2006)","DOI":"10.1007\/11745853_12"},{"issue":"3","key":"1788_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00198464","volume":"6","author":"D Coppersmith","year":"1993","unstructured":"Coppersmith D.: Modifications to the number field sieve. J. Cryptol. 6(3), 169\u2013180 (1993).","journal-title":"J. Cryptol."},{"key":"1788_CR12","doi-asserted-by":"crossref","unstructured":"De\u00a0Micheli, G., Gaudry, P., Pierrot, C.: Asymptotic complexities of discrete logarithm algorithms in pairing-relevant finite fields. In: Advances in Cryptology \u2013 CRYPTO 2020. pp. 32\u201361. Springer (2020)","DOI":"10.1007\/978-3-030-56880-1_2"},{"issue":"6","key":"1788_CR13","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"1976","unstructured":"Diffie W., Hellman M.E.: New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644\u2013654 (1976).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1788_CR14","doi-asserted-by":"crossref","unstructured":"Fried, J., Gaudry, P., Heninger, N., Thom\u00e9, E.: A kilobit hidden SNFS discrete logarithm computation. In: Advances in Cryptology \u2013 EUROCRYPT 2017. pp. 202\u2013231. Springer (2017)","DOI":"10.1007\/978-3-319-56620-7_8"},{"issue":"1","key":"1788_CR15","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/0406010","volume":"6","author":"DM Gordon","year":"1993","unstructured":"Gordon D.M.: Discrete logarithms in GF$$(p)$$ using the number field sieve. SIAM J. Discret. Math. 6(1), 124\u2013138 (1993).","journal-title":"SIAM J. Discret. Math."},{"key":"1788_CR16","doi-asserted-by":"publisher","first-page":"3129","DOI":"10.1090\/tran\/7027","volume":"370","author":"R Granger","year":"2017","unstructured":"Granger R., Kleinjung T., Zumbr\u00e4gel J.: On the discrete logarithm problem in finite fields of fixed characteristic. Trans. Am. Math. Soc. 370, 3129\u20133145 (2017).","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"1788_CR17","first-page":"1","volume":"1","author":"A Guillevic","year":"2021","unstructured":"Guillevic A., Singh S.: On the alpha value of polynomials in the tower number field sieve algorithm. Mathematical Cryptology 1(1), 1\u201339 (2021).","journal-title":"Mathematical Cryptology"},{"key":"1788_CR18","doi-asserted-by":"crossref","unstructured":"Joux, A.: A new index calculus algorithm with complexity $${L}(1\/4+o(1))$$ in small characteristic. In: Selected Areas in Cryptography \u2013 SAC 2013. pp. 355\u2013379 (2014)","DOI":"10.1007\/978-3-662-43414-7_18"},{"key":"1788_CR19","doi-asserted-by":"crossref","unstructured":"Joux, A., Lercier, R., Smart, N., Vercauteren, F.: The number field sieve in the medium prime case. In: Advances in Cryptology \u2013 CRYPTO 2006. pp. 326\u2013344. Springer (2006)","DOI":"10.1007\/11818175_19"},{"key":"1788_CR20","doi-asserted-by":"crossref","unstructured":"Joux, A., Pierrot, C.: The special number field sieve in $$\\mathbb{F}_{p^n}$$, Application to pairing-friendly constructions. In: 6th International Conference on Pairing-based Cryptography, Pairing 2013. vol.\u00a08365, pp. 45\u201361. Springer (2013)","DOI":"10.1007\/978-3-319-04873-4_3"},{"key":"1788_CR21","doi-asserted-by":"crossref","unstructured":"Joux, A., Pierrot, C.: Nearly sparse linear algebra and application to discrete logarithms computations. In: Contemporary Developments in Finite Fields and Applications, pp. 119\u2013144. World Scientific (2016)","DOI":"10.1142\/9789814719261_0008"},{"key":"1788_CR22","doi-asserted-by":"crossref","unstructured":"Kim, T., Barbulescu, R.: Extended tower number field sieve: A new complexity for the medium prime case. In: Advances in Cryptology \u2013 CRYPTO 2016. pp. 543\u2013571. Springer (2016)","DOI":"10.1007\/978-3-662-53018-4_20"},{"key":"1788_CR23","doi-asserted-by":"crossref","unstructured":"Kim, T., Jeong, J.: Extended tower number field sieve with application to finite fields of arbitrary composite extension degree. In: Public Key Cryptography \u2013 PKC 2017. pp. 388\u2013408. Springer (2017)","DOI":"10.1007\/978-3-662-54365-8_16"},{"issue":"256","key":"1788_CR24","doi-asserted-by":"publisher","first-page":"2037","DOI":"10.1090\/S0025-5718-06-01870-9","volume":"75","author":"T Kleinjung","year":"2006","unstructured":"Kleinjung T.: On polynomial selection for the general number field sieve. Math. Comput. 75(256), 2037\u20132047 (2006).","journal-title":"Math. Comput."},{"issue":"1","key":"1788_CR25","first-page":"71","volume":"1","author":"A Le Gluher","year":"2021","unstructured":"Le Gluher A., Spaenlehauer P.J., Thom\u00e9 E.: Refined analysis of the asymptotic complexity of the number field sieve. Mathematical Cryptology 1(1), 71\u201388 (2021).","journal-title":"Mathematical Cryptology"},{"key":"1788_CR26","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.jnt.2017.10.019","volume":"187","author":"JD Lee","year":"2018","unstructured":"Lee J.D., Venkatesan R.: Rigorous analysis of a randomised number field sieve. Journal of Number Theory 187, 92\u2013159 (2018).","journal-title":"Journal of Number Theory"},{"key":"1788_CR27","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Jr., H.W.L., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA. pp. 564\u2013572 (1990)","DOI":"10.1145\/100216.100295"},{"key":"1788_CR28","first-page":"121","volume":"9","author":"DV Matyukhin","year":"2006","unstructured":"Matyukhin D.V.: Effective version of the number field sieve for discrete logarithm in a field GF$$(p^k)$$. Trudy po Diskretnoi Matematike 9, 121\u2013151 (2006).","journal-title":"Trudy po Diskretnoi Matematike"},{"key":"1788_CR29","doi-asserted-by":"crossref","unstructured":"Panario, D., Gourdon, X., Flajolet, P.: An analytic approach to smooth polynomials over finite fields. In: International Algorithmic Number Theory Symposium. pp. 226\u2013236. Springer (1998)","DOI":"10.1007\/BFb0054865"},{"key":"1788_CR30","doi-asserted-by":"crossref","unstructured":"Pierrot, C.: The multiple number field sieve with Conjugation and Generalized Joux-Lercier methods. In: Advances in Cryptology \u2013 EUROCRYPT 2015. pp. 156\u2013170. Springer (2015)","DOI":"10.1007\/978-3-662-46800-5_7"},{"key":"1788_CR31","doi-asserted-by":"crossref","unstructured":"Sarkar, P., Singh, S.: New complexity trade-offs for the (multiple) number field sieve algorithm in non-prime fields. In: Advances in Cryptology \u2013 EUROCRYPT 2016. pp. 429\u2013458. Springer (2016)","DOI":"10.1007\/978-3-662-49890-3_17"},{"issue":"3","key":"1788_CR32","doi-asserted-by":"publisher","first-page":"435","DOI":"10.3934\/amc.2019028","volume":"13","author":"P Sarkar","year":"2019","unstructured":"Sarkar P., Singh S.: A unified polynomial selection method for the (tower) number field sieve algorithm. Adv. Math. Commun. 13(3), 435\u2013455 (2019).","journal-title":"Adv. Math. Commun."},{"issue":"1676","key":"1788_CR33","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1098\/rsta.1993.0139","volume":"345","author":"O Schirokauer","year":"1993","unstructured":"Schirokauer O.: Discrete logarithms and local units. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 345(1676), 409\u2013423 (1993).","journal-title":"Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences"},{"issue":"1","key":"1788_CR34","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"32","author":"DH Wiedemann","year":"1986","unstructured":"Wiedemann D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54\u201362 (1986).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1788_CR35","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.tcs.2020.01.010","volume":"814","author":"Y Zhu","year":"2020","unstructured":"Zhu Y., Wen J., Zhuang J., Lv C., Lin D.: Refined analysis to the extended tower number field sieve. Theoret. Comput. Sci. 814, 49\u201368 (2020).","journal-title":"Theoret. Comput. Sci."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01788-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-025-01788-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01788-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T05:02:32Z","timestamp":1774846952000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-025-01788-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,16]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["1788"],"URL":"https:\/\/doi.org\/10.1007\/s10623-025-01788-5","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,16]]},"assertion":[{"value":"20 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 November 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"51"}}