{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:53:19Z","timestamp":1776847999016,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662467992","type":"print"},{"value":"9783662468005","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46800-5_6","type":"book-chapter","created":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T04:29:09Z","timestamp":1428899349000},"page":"129-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":44,"title":["Improving NFS for the Discrete Logarithm Problem in Non-prime Finite Fields"],"prefix":"10.1007","author":[{"given":"Razvan","family":"Barbulescu","sequence":"first","affiliation":[]},{"given":"Pierrick","family":"Gaudry","sequence":"additional","affiliation":[]},{"given":"Aurore","family":"Guillevic","sequence":"additional","affiliation":[]},{"given":"Fran\u00e7ois","family":"Morain","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,14]]},"reference":[{"key":"6_CR1","unstructured":"Bai, S., Filbois, A., Gaudry, P., Kruppa, A., Morain, F., Thom\u00e9, E., Zimmermann, P., et al.: Crible alg\u00e9brique: Distribution, optimisation - NFS (2009). downloadable at \n                      http:\/\/cado-nfs.gforge.inria.fr\/"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-55220-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"R Barbulescu","year":"2014","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: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1\u201316. Springer, Heidelberg (2014)"},{"key":"6_CR3","unstructured":"Barbulescu, R., Pierrot, C.: The multiple number field sieve for medium- and high-characteristic finite fields. LMS Journal of Computation and Mathematics 17, 230\u2013246 (2014). \n                      http:\/\/journals.cambridge.org\/article_S1461157014000369"},{"key":"6_CR4","unstructured":"Barbulescu, R.: Algorithmes de logarithmes discrets dans les corps finis. Ph.D. thesis, Universit\u00e9 de Lorraine (2013)"},{"key":"6_CR5","unstructured":"Barbulescu, R., Gaudry, P., Guillevic, A., Morain, F.: Improvements to the number field sieve for non-prime finite fields. preprint available at \n                      http:\/\/hal.inria.fr\/hal-01052449"},{"key":"6_CR6","unstructured":"Bouvier, C., Gaudry, P., Imbert, L., Jeljeli, H., Thom\u00e9, E.: Discrete logarithms in GF(p) \u2013 180 digits (2014), announcement available at the NMBRTHRY archives, item 004703"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Canfield, E.R., Erd\u00f6s, P., Pomerance, C.: On a problem of Oppenheim concerning \u201cfactorisatio numerorum\u201d. J. Number Theory 17(1), 1\u201328 (1983)","DOI":"10.1016\/0022-314X(83)90002-1"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1006\/jsco.1995.1051","volume":"20","author":"GE Collins","year":"1995","unstructured":"Collins, G.E., Encarnaci\u00f3n, M.J.: Efficient rational number reconstruction. Journal of Symbolic Computation 20(3), 287\u2013297 (1995)","journal-title":"Journal of Symbolic Computation"},{"issue":"3","key":"6_CR9","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. of Cryptology 6(3), 169\u2013180 (1993)","journal-title":"J. of Cryptology"},{"issue":"205","key":"6_CR10","first-page":"333","volume":"62","author":"D Coppersmith","year":"1994","unstructured":"Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm. Math. Comp. 62(205), 333\u2013350 (1994)","journal-title":"Math. Comp."},{"issue":"4","key":"6_CR11","doi-asserted-by":"crossref","first-page":"1621","DOI":"10.1215\/ijm\/1373636699","volume":"55","author":"K Foster","year":"2011","unstructured":"Foster, K.: HT90 and \u201csimplest\u201d number fields. Illinois J. Math. 55(4), 1621\u20131655 (2011)","journal-title":"Illinois J. Math."},{"issue":"2","key":"6_CR12","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00145-009-9048-z","volume":"23","author":"D Freeman","year":"2010","unstructured":"Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. of Cryptology 23(2), 224\u2013280 (2010)","journal-title":"J. of Cryptology"},{"key":"6_CR13","unstructured":"Jeljeli, H.: Accelerating iterative SpMV for discrete logarithm problem using GPUs (2014). \n                      http:\/\/hal.inria.fr\/hal-00734975\/\n                      \n                    , preprint, to appear in WAIFI 2014"},{"key":"6_CR14","unstructured":"Jeljeli, H.: An implementation of the Block-Wiedemann algorithm on NVIDIA-GPUs using the Residue Number System (RNS) arithmetic (2014). available from \n                      http:\/\/www.loria.fr\/~hjeljeli\/"},{"issue":"242","key":"6_CR15","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1090\/S0025-5718-02-01482-5","volume":"72","author":"A Joux","year":"2003","unstructured":"Joux, A., Lercier, R.: Improvements to the general number field for discrete logarithms in prime fields. Math. Comp. 72(242), 953\u2013967 (2003)","journal-title":"Math. Comp."},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1007\/11818175_19","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"A Joux","year":"2006","unstructured":"Joux, A., Lercier, R., Smart, N.P., Vercauteren, F.: The Number Field Sieve in the Medium Prime Case. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 326\u2013344. Springer, Heidelberg (2006)"},{"key":"6_CR17","unstructured":"Joux, A., Lercier, R., et al.: Algorithmes pour r\u00e9soudre le probl\u00e8me du logarithme discret dans les corps finis. Nouvelles M\u00e9thodes Math\u00e9matiques en Cryptographie, volume Fascicule Journ\u00e9es Annuelles, p. 23 (2007)"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-319-04873-4_3","volume-title":"Pairing-Based Cryptography \u2013 Pairing 2013","author":"A Joux","year":"2014","unstructured":"Joux, A., Pierrot, C.: The Special Number Field Sieve in \n                      \n                        \n                      \n                      $$\\mathbb{F}_{p^{n}}$$\n                    . In: Cao, Z., Zhang, F. (eds.) Pairing 2013. LNCS, vol. 8365, pp. 45\u201361. Springer, Heidelberg (2014)"},{"key":"6_CR19","first-page":"82","volume":"73","author":"M Kalkbrener","year":"1997","unstructured":"Kalkbrener, M.: An upper bound on the number of monomials in determinants of sparse matrices with symbolic entries. Mathematica Pannonica 73, 82 (1997)","journal-title":"Mathematica Pannonica"},{"issue":"256","key":"6_CR20","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. Mathematics of Computation 75(256), 2037\u20132047 (2006)","journal-title":"Mathematics of Computation"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44598-6_1","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"AK Lenstra","year":"2000","unstructured":"Lenstra, A.K., Verheul, E.R.: The XTR Public Key System. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 1\u201319. Springer, Heidelberg (2000)"},{"issue":"4","key":"6_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"issue":"1","key":"6_CR23","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1515\/156939203321669546","volume":"13","author":"DV Matyukhin","year":"2003","unstructured":"Matyukhin, D.V.: On asymptotic complexity of computing discrete logarithms over GF(p). Discrete Mathematics and Applications 13(1), 27\u201350 (2003)","journal-title":"Discrete Mathematics and Applications"},{"key":"6_CR24","unstructured":"Matyukhin, D.: Effective version of the number field sieve for discrete logarithms in the field GF\n                      \n                        \n                      \n                      $$(p^k)$$\n                    . Trudy po Discretnoi Matematike 9, 121\u2013151 (2006) (in Russian). \n                      http:\/\/m.mathnet.ru\/php\/archive.phtml?wshow=paper&jrnid=tdm&paperid=144&option_lang=eng"},{"key":"6_CR25","unstructured":"Murphy, B.A.: Polynomial selection for the number field sieve integer factorisation algorithm. Ph.D. thesis, Australian National Univers (1999)"},{"key":"6_CR26","unstructured":"Pierrot, C.: The multiple number field sieve with conjugation method (August 2014). preprint available at \n                      https:\/\/eprint.iacr.org\/2014\/641"},{"issue":"1","key":"6_CR27","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1109\/TIT.1978.1055817","volume":"24","author":"S Pohlig","year":"1978","unstructured":"Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and his cryptographic significance. IEEE Trans. Inform. Theory 24(1), 106\u2013110 (1978)","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"143","key":"6_CR28","first-page":"918","volume":"32","author":"JM Pollard","year":"1978","unstructured":"Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comp. 32(143), 918\u2013924 (1978)","journal-title":"Math. Comp."},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/978-3-540-45146-4_21","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"K Rubin","year":"2003","unstructured":"Rubin, K., Silverberg, A.: Torus-Based Cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 349\u2013365. Springer, Heidelberg (2003)"},{"issue":"231","key":"6_CR30","doi-asserted-by":"publisher","first-page":"1267","DOI":"10.1090\/S0025-5718-99-01137-0","volume":"69","author":"O Schirokauer","year":"2000","unstructured":"Schirokauer, O.: Using number fields to compute logarithms in finite fields. Math. Comp. 69(231), 1267\u20131283 (2000)","journal-title":"Math. Comp."},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.jalgor.2004.11.004","volume":"57","author":"O Schirokauer","year":"2005","unstructured":"Schirokauer, O.: Virtual logarithms. J. Algorithms 57, 140\u2013147 (2005)","journal-title":"J. Algorithms"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Smith, P., Skinner, C.: A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms. In: Pieprzyk, J., Safavi-Naini, R. (eds.) Advances in Cryptology - ASIACRYPT 1994. LNCS, vol. 917, pp. 357\u2013364. Springer, Heidelberg (1994)","DOI":"10.1007\/BFb0000447"},{"issue":"1","key":"6_CR33","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"32","author":"D Wiedemann","year":"1986","unstructured":"Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory 32(1), 54\u201362 (1986)","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology -- EUROCRYPT 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46800-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T17:28:20Z","timestamp":1559150900000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46800-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662467992","9783662468005"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46800-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"14 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}