{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:37:12Z","timestamp":1764981432569,"version":"3.46.0"},"reference-count":24,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T00:00:00Z","timestamp":1606262400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,11,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Lattice sieving in two dimensions has proven to be an indispensable practical aid in integer factorization and discrete log computations involving the number field sieve. The main contribution of this article is to show that a different method of lattice sieving in three dimensions will provide a significant speedup in medium characteristic. Our method is to use the successive minima and shortest vectors of the lattice instead of transition vectors to iterate through lattice points. We showcase the new method by a record computation in a 133-bit subgroup of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2020-0008_eq_001.png\"\/>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:mrow>\n                            <m:msub>\n                              <m:mi mathvariant=\"double-struck\">F<\/m:mi>\n                              <m:mrow>\n                                <m:msup>\n                                  <m:mi>p<\/m:mi>\n                                  <m:mn>6<\/m:mn>\n                                <\/m:msup>\n                              <\/m:mrow>\n                            <\/m:msub>\n                          <\/m:mrow>\n                        <\/m:math>\n                        <jats:tex-math>${{\\mathbb{F}}_{{{p}^{6}}}}$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , with\n                    <jats:italic>p<\/jats:italic>\n                    <jats:sup>6<\/jats:sup>\n                    having 423 bits. Our overall timing is nearly 3 times faster than the previous record of a 132-bit subgroup in a 422-bit field. The approach generalizes to dimensions 4 or more, overcoming one key obstruction to the implementation of the tower number field sieve.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2020-0008","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T15:54:46Z","timestamp":1606751686000},"page":"223-236","source":"Crossref","is-referenced-by-count":4,"title":["Lattice Sieving in Three Dimensions for Discrete Log in Medium Characteristic"],"prefix":"10.1515","volume":"15","author":[{"given":"Gary","family":"McGuire","sequence":"first","affiliation":[{"name":"UCD School of Mathematics and Statistics, University College Dublin , Dublin Ireland"}]},{"given":"Ois\u00edn","family":"Robinson","sequence":"additional","affiliation":[{"name":"UCD School of Mathematics and Statistics, University College Dublin , Dublin Ireland"}]}],"member":"374","published-online":{"date-parts":[[2020,11,25]]},"reference":[{"key":"2025120600333841572_j_jmc-2020-0008_ref_001","doi-asserted-by":"crossref","unstructured":"Aoki, K., Ueda, H.: Sieving using bucket sort. In: Advances in cryptology\u2014ASIACRYPT 2004, Lecture Notes in Comput. Sci., vol. 3329, pp. 92\u2013102. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-30539-2_8"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_002","doi-asserted-by":"crossref","unstructured":"Babai, L.: On Lov\u00e1sz\u2019 lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1\u201313 (1986). 10.1007\/BF02579403, https:\/\/doi.org\/10.1007\/BF02579403","DOI":"10.1007\/BF02579403"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_003","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\u2014EUROCRYPT 2015. Part I, Lecture Notes in Comput. Sci., vol. 9056, pp. 129\u2013155. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-46800-5_6"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_004","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\u2014EUROCRYPT 2014, Lecture Notes in Comput. Sci., vol. 8441, pp. 1\u201316. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-642-55220-5_1"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_005","doi-asserted-by":"crossref","unstructured":"Cohen, H.: A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138. Springer-Verlag, Berlin (1993)","DOI":"10.1007\/978-3-662-02945-9"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_006","doi-asserted-by":"crossref","unstructured":"Fincke, U., Pohst, M.: A new method of computing fundamental units in algebraic number fields. In: EUROCAL \u201985, Vol. 2 (Linz, 1985), Lecture Notes in Comput. Sci., vol. 204, pp. 470\u2013478. Springer, Berlin (1985)","DOI":"10.1007\/3-540-15984-3_315"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_007","unstructured":"Franke, J., Kleinjung, T.: Continued fractions and lattice sieving. In: Workshop record of SHARCS (2005) (2005), available at http:\/\/www.ruhr-uni-bochum.de\/itsc\/tanja\/SHARCS\/talks\/FrankeKleinjung.pdf"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_008","doi-asserted-by":"crossref","unstructured":"Gaudry, P., Gr\u00e9my, L., Videau, M.: Collecting relations for the number field sieve in GFp6 LMS J. Comput. Math. 19(suppl. A), 332\u2013350 (2016)","DOI":"10.1112\/S1461157016000164"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_009","doi-asserted-by":"crossref","unstructured":"Gras, M.N.: Special units in real cyclic sextic fields. Math. Comp. 48(177), 179\u2013182 (1987)","DOI":"10.1090\/S0025-5718-1987-0866107-1"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_010","unstructured":"Gremy, L.: Sieve algorithms for the discrete logarithm in medium characteristic finite fields. In: Ph.D. thesis, Universite de Lorraine (2017), available at https:\/\/tel.archives-ouvertes.fr\/tel-01647623"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_011","doi-asserted-by":"crossref","unstructured":"Gr\u00e9my, L., Guillevic, A., Morain, F., Thom\u00e9, E.: Computing discrete logarithms in \ud835\udd3dp6 In: Selected areas in cryptography\u2014SAC 2017, Lecture Notes in Comput. Sci., vol. 10719, pp. 85\u2013105. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-72565-9_5"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_012","doi-asserted-by":"crossref","unstructured":"Guillevic, A.: Computing individual discrete logarithms faster in GFpnwith the NFS-DL algorithm. In: Advances in cryptology\u2014ASIACRYPT 2015. Part I, Lecture Notes in Comput. Sci., vol. 9452, pp. 149\u2013173. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48797-6_7"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_013","doi-asserted-by":"crossref","unstructured":"Guillevic, A.: Faster individual discrete logarithms in finite fields of composite extension degree. Math. Comp. 88(317), 1273\u20131301 (2019)","DOI":"10.1090\/mcom\/3376"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_014","unstructured":"Guillevic, A., Singh, S.: On the Alpha Value of Polynomials in the Tower Number Field Sieve Algorithm (Aug 2019), https:\/\/hal.inria.fr\/hal-02263098 working paper or preprint"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_015","doi-asserted-by":"crossref","unstructured":"Hayasaka, K., Aoki, K., Kobayashi, T., Takagi, T.: An experiment of number field sieve for discrete logarithm problem over gf p12 JSIAM Letters (Jan 2013)","DOI":"10.1007\/978-3-642-42001-6_8"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_016","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\u2014CRYPTO 2006, Lecture Notes in Comput. Sci., vol. 4117, pp. 326\u2013344. Springer, Berlin (2006)","DOI":"10.1007\/11818175_19"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_017","doi-asserted-by":"crossref","unstructured":"Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. p. 193\u2013206. STOC \u201983, Association for Computing Machinery, New York, NY, USA (1983), https:\/\/doi.org\/10.1145\/800061.808749","DOI":"10.1145\/800061.808749"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_018","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\u2014CRYPTO 2016. Part I, Lecture Notes in Comput. Sci., vol. 9814, pp. 543\u2013571. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53018-4_20"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_019","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\u2014PKC 2017. Part I, Lecture Notes in Comput. Sci., vol. 10174, pp. 388\u2013408. Springer, Berlin (2017)","DOI":"10.1007\/978-3-662-54365-8_16"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_020","doi-asserted-by":"crossref","unstructured":"Pollard, J.M.: The lattice sieve. In: The development of the number field sieve, Lecture Notes in Math., vol. 1554, pp. 43\u201349. Springer, Berlin (1993)","DOI":"10.1007\/BFb0091538"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_021","doi-asserted-by":"crossref","unstructured":"Sarkar, P., Singh, S.: A general polynomial selection method and new asymptotic complexities for the tower number field sieve algorithm. In: Advances in cryptology\u2014ASIACRYPT 2016. Part I, Lecture Notes in Comput. Sci., vol. 10031, pp. 37\u201362. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53887-6_2"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_022","doi-asserted-by":"crossref","unstructured":"Schirokauer, O.: Discrete logarithms and local units. Philos. Trans. Roy. Soc. London Ser. A 345(1676), 409\u2013423 (1993)","DOI":"10.1098\/rsta.1993.0139"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_023","unstructured":"The CADO-NFS development team: Cado-nfs, an implementation of the number field sieve algorithm (2019), available at http:\/\/cado-nfs.gforge.inria.fr\/"},{"key":"2025120600333841572_j_jmc-2020-0008_ref_024","unstructured":"Zajac, P.: Discrete logarithm problem in degree six finite fields. In: Ph.D. thesis, Slovak University of Technology (2008), http:\/\/www.kaivt.elf.stuba.sk\/kaivt\/Vyskum\/XTRDL"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/jmc\/15\/1\/article-p223.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0008\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0008\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:35:10Z","timestamp":1764981310000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0008\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,25]]},"references-count":24,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,4,20]]},"published-print":{"date-parts":[[2021,4,20]]}},"alternative-id":["10.1515\/jmc-2020-0008"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0008","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2020,11,25]]}}}