{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T12:57:57Z","timestamp":1772283477523,"version":"3.50.1"},"reference-count":34,"publisher":"Wiley","issue":"A","license":[{"start":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T00:00:00Z","timestamp":1472169600000},"content-version":"unspecified","delay-in-days":238,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2016]]},"abstract":"<jats:p>In order to assess the security of cryptosystems based on the discrete logarithm problem in non-prime finite fields, as are the torus-based or pairing-based ones, we investigate thoroughly the case in<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157016000164_inline3\"\/><jats:tex-math>$\\mathbb{F}_{p^{6}}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>with the number field sieve. We provide new insights, improvements, and comparisons between different methods to select polynomials intended for a sieve in dimension 3 using a special-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157016000164_inline4\"\/><jats:tex-math>$\\mathfrak{q}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>strategy. We also take into account the Galois action to increase the relation productivity of the sieving phase. To validate our results, we ran several experiments and real computations for various polynomial selection methods and field sizes with our publicly available implementation of the sieve in dimension 3, with special-<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S1461157016000164_inline5\"\/><jats:tex-math>$\\mathfrak{q}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and various enumeration strategies.<\/jats:p>","DOI":"10.1112\/s1461157016000164","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T15:30:35Z","timestamp":1472225435000},"page":"332-350","source":"Crossref","is-referenced-by-count":12,"title":["Collecting relations for the number field sieve in"],"prefix":"10.1112","volume":"19","author":[{"given":"Pierrick","family":"Gaudry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Gr\u00e9my","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marion","family":"Videau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,8,26]]},"reference":[{"key":"S1461157016000164_r31","unstructured":"31. The CADO-NFS Development Team: CADO-NFS, an implementation of the number field sieve algorithm, 2015, https:\/\/2.zoppoz.workers.dev:443\/http\/cado-nfs.gforge.inria.fr\/, release 2.2.0."},{"key":"S1461157016000164_r20","first-page":"45","volume-title":"Pairing 2013","author":"Joux","year":"2013"},{"key":"S1461157016000164_r33","first-page":"161","article-title":"On the use of the lattice sieve in the 3D NFS","volume":"45","author":"Zajac","year":"2010","journal-title":"Tatra Mt. Math. Publ."},{"key":"S1461157016000164_r10","unstructured":"10. J. Franke and T. Kleinjung , \u2018Continued fractions and lattice sieving\u2019, SHARCS\u201905 \u2013 Special-purpose Hardware for Attacking Cryptographic Systems (2005), https:\/\/2.zoppoz.workers.dev:443\/http\/www.sharcs.org\/."},{"key":"S1461157016000164_r7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9"},{"key":"S1461157016000164_r9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF00198464","article-title":"Modifications to the number field sieve","volume":"6","author":"Coppersmith","year":"1993","journal-title":"J.\u00a0Cryptology"},{"key":"S1461157016000164_r30","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1993.0139"},{"key":"S1461157016000164_r14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48797-6_7"},{"key":"S1461157016000164_r22","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-06-01870-9"},{"key":"S1461157016000164_r17","unstructured":"17. K. Hayasaka , K. Aoki , T. Kobayashi and T. Takagi , \u2018A construction of 3-dimensional lattice sieve for number field sieve over $\\mathbb{F}_{p^{n}}$ \u2019, Cryptology ePrint Archive, 2015\/1179, 2015."},{"key":"S1461157016000164_r32","unstructured":"32. P. Zajac , \u2018Discrete logarithm problem in degree six finite fields\u2019, PhD Thesis, Slovak University of Technology, 2008, https:\/\/2.zoppoz.workers.dev:443\/http\/www.kaivt.elf.stuba.sk\/kaivt\/Vyskum\/XTRDL."},{"key":"S1461157016000164_r28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49890-3_17"},{"key":"S1461157016000164_r11","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-009-9048-z"},{"key":"S1461157016000164_r23","first-page":"1","volume-title":"CRYPTO 2000","author":"Lenstra","year":"2000"},{"key":"S1461157016000164_r13","doi-asserted-by":"publisher","DOI":"10.1137\/0406010"},{"key":"S1461157016000164_r4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_2"},{"key":"S1461157016000164_r15","first-page":"159","volume-title":"Coding and Cryptology \u2014 Third International Workshop, IWCC 2011","author":"Hanrot","year":"2011"},{"key":"#cr-split#-S1461157016000164_r21.1","doi-asserted-by":"crossref","unstructured":"5. T. Kim and R. Barbulescu, 'Extended tower number field sieve: a new complexity for medium prime case', CRYPTO 2016, Lecture Notes in Computer Science (Springer), to appear","DOI":"10.1007\/978-3-662-53018-4_20"},{"key":"#cr-split#-S1461157016000164_r21.2","unstructured":"6. Cryptology ePrint Archive, 2015\/1027, 2015."},{"key":"S1461157016000164_r6","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157014000369"},{"key":"S1461157016000164_r3","first-page":"1","volume-title":"EUROCRYPT 2014","author":"Barbulescu","year":"2014"},{"key":"S1461157016000164_r16","first-page":"108","volume-title":"Number theory and cryptography","author":"Hayasaka","year":"2013"},{"key":"S1461157016000164_r18","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-02-01482-5"},{"key":"S1461157016000164_r25","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/978-3-662-46800-5_7","volume-title":"EUROCRYPT 2015","author":"Pierrot","year":"2015"},{"key":"S1461157016000164_r29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.11.004"},{"key":"S1461157016000164_r1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2015-02926-3"},{"key":"S1461157016000164_r24","unstructured":"24. B. A. Murphy , \u2018Polynomial selection for the number field sieve integer factorisation algorithm\u2019, PhD Thesis, Australian National University, 1999."},{"key":"S1461157016000164_r8","first-page":"174","volume-title":"PKC 2006","author":"Commeine","year":"2006"},{"key":"S1461157016000164_r27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_21"},{"key":"S1461157016000164_r2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-662-46800-5_6","volume-title":"EUROCRYPT 2015","author":"Barbulescu","year":"2015"},{"key":"S1461157016000164_r5","doi-asserted-by":"crossref","unstructured":"5. R. Barbulescu and A. Lachand , \u2018Some mathematical remarks on the polynomial selection in NFS\u2019, Math. Comp., published online (2016), doi:10.1090\/mcom\/3112.","DOI":"10.1090\/mcom\/3112"},{"key":"S1461157016000164_r26","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0091538"},{"key":"S1461157016000164_r19","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_19"},{"key":"S1461157016000164_r12","first-page":"42","article-title":"Measurement of areas on a sphere using Fibonacci and latitude\u2013longitude lattices","author":"Gonz\u00e1lez","year":"2010","journal-title":"Math. Geosci."}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157016000164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,25]],"date-time":"2020-09-25T15:28:59Z","timestamp":1601047739000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/product\/identifier\/S1461157016000164\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"references-count":34,"journal-issue":{"issue":"A","published-print":{"date-parts":[[2016]]}},"alternative-id":["S1461157016000164"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1112\/s1461157016000164","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}