{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T04:57:59Z","timestamp":1649048279735},"reference-count":32,"publisher":"American Mathematical Society (AMS)","license":[{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\ufffdrderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-156420","200021-156420","200021-156420"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

This paper reports on the computation of a discrete logarithm in the finite field \n\n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n \n \n 2<\/mml:mn>\n \n 30750<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:msub>\n \\mathbb {F}_{2^{30750}}<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, breaking by a large margin the previous record, which was set in January 2014 by a computation in\u00a0\n\n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n \n \n 2<\/mml:mn>\n \n 9234<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:msub>\n \\mathbb {F}_{2^{9234}}<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbr\u00e4gel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about \n\n \n 2900<\/mml:mn>\n 2900<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately \n\n \n 3100<\/mml:mn>\n 3100<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> core years expended for the discrete logarithm record for prime fields, set in a field of bit-length \n\n \n 795<\/mml:mn>\n 795<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula>, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Gr\u00f6bner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the \n\n \n \n L<\/mml:mi>\n (<\/mml:mo>\n \n 1<\/mml:mn>\n 4<\/mml:mn>\n <\/mml:mfrac>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n L(\\frac 1 4 + o(1))<\/mml:annotation>\n <\/mml:semantics>\n<\/mml:math>\n<\/inline-formula> complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.<\/p>","DOI":"10.1090\/mcom\/3669","type":"journal-article","created":{"date-parts":[[2021,5,26]],"date-time":"2021-05-26T19:24:35Z","timestamp":1622057075000},"source":"Crossref","is-referenced-by-count":1,"title":["Computation of a 30750-bit binary field discrete logarithm"],"prefix":"10.1090","author":[{"given":"Robert","family":"Granger","sequence":"first","affiliation":[]},{"given":"Thorsten","family":"Kleinjung","sequence":"additional","affiliation":[]},{"given":"Arjen","family":"Lenstra","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Wesolowski","sequence":"additional","affiliation":[]},{"given":"Jens","family":"Zumbr\u00e4gel","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2021,7,16]]},"reference":[{"key":"1","doi-asserted-by":"publisher","first-page":"1","article-title":"A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic","author":"Barbulescu, Razvan","year":"2014","DOI":"10.1007\/978-3-642-55220-5_1"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.ffa.2003.08.004","article-title":"On \ud835\udc65^{\ud835\udc5e+1}+\ud835\udc4e\ud835\udc65+\ud835\udc4f","volume":"10","author":"Bluher, Antonia W.","year":"2004","journal-title":"Finite Fields Appl.","ISSN":"http:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"3-4","key":"3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma, Wieb","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"http:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"4","article-title":"795-Bit factoring and discrete logarithms","author":"Boudot, Fabrice","year":"December 2, 2019"},{"key":"5","article-title":"Factorization of RSA-250","author":"Boudot, Fabrice","year":"February 28, 2020"},{"issue":"3","key":"6","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/s00145-017-9273-9","article-title":"Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression","volume":"31","author":"Canteaut, Anne","year":"2018","journal-title":"J. Cryptology","ISSN":"http:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/TIT.1984.1056941","article-title":"Fast evaluation of logarithms in fields of characteristic two","volume":"30","author":"Coppersmith, Don","year":"1984","journal-title":"IEEE Trans. Inform. Theory","ISSN":"http:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"3","key":"8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00198464","article-title":"Modifications to the number field sieve","volume":"6","author":"Coppersmith, Don","year":"1993","journal-title":"J. Cryptology","ISSN":"http:\/\/id.crossref.org\/issn\/0933-2790","issn-type":"print"},{"issue":"1","key":"9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.4064\/aa102-1-6","article-title":"A general framework for subexponential discrete logarithm algorithms","volume":"102","author":"Enge, Andreas","year":"2002","journal-title":"Acta Arith.","ISSN":"http:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"10","doi-asserted-by":"publisher","first-page":"109","article-title":"On the function field sieve and the impact of higher splitting probabilities: application to discrete logarithms in \ud835\udd3d_{2\u00b9\u2079\u2077\u00b9} and \ud835\udd3d_{2\u00b3\u00b9\u2076\u2074}","author":"G\u00f6lo\u011flu, Faruk","year":"2013","DOI":"10.1007\/978-3-642-40084-1_7"},{"key":"11","series-title":"LNCS","first-page":"136","article-title":"Solving a 6120-bit DLP on a desktop computer","volume":"8282","author":"G\u00f6lo\u011flu, Faruk","year":"2014"},{"key":"12","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u2076\u00b9\u00b2\u2070)","author":"G\u00f6lo\u011flu, Faruk","year":"April 11, 2013"},{"key":"13","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u00b9\u2079\u2077\u00b9)","author":"G\u00f6lo\u011flu, Faruk","year":"February 19, 2013"},{"key":"14","doi-asserted-by":"publisher","first-page":"263","article-title":"Improved masking for tweakable blockciphers with applications to authenticated encryption","author":"Granger, Robert","year":"2016","DOI":"10.1007\/978-3-662-49890-3_11"},{"key":"15","doi-asserted-by":"publisher","first-page":"126","article-title":"Breaking \u2018128-bit secure\u2019 supersingular binary curves (or how to solve discrete logarithms in \ud835\udd3d_{2^{4\u22c51223}} and \ud835\udd3d_{2^{12\u22c5367}})","author":"Granger, Robert","year":"2014","DOI":"10.1007\/978-3-662-44381-1_8"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"3129","DOI":"10.1090\/tran\/7027","article-title":"On the discrete logarithm problem in finite fields of fixed characteristic","volume":"370","author":"Granger, Robert","year":"2018","journal-title":"Trans. Amer. Math. Soc.","ISSN":"http:\/\/id.crossref.org\/issn\/0002-9947","issn-type":"print"},{"key":"17","article-title":"On the powers of 2","author":"Granger, Robert","year":"April 29, 2014"},{"key":"18","article-title":"Discrete logarithms in the Jacobian of a genus 2 supersingular curve over \ud835\udc3a\ud835\udc39(2\u00b3\u2076\u2077)","author":"Granger, Robert","year":"January 30, 2014"},{"key":"19","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u2079\u00b2\u00b3\u2074)","author":"Granger, Robert","year":"January 31, 2014"},{"key":"20","doi-asserted-by":"publisher","first-page":"355","article-title":"A new index calculus algorithm with complexity \ud835\udc3f(1\/4+\ud835\udc5c(1)) in small characteristic","author":"Joux, Antoine","year":"2014","DOI":"10.1007\/978-3-662-43414-7_18"},{"key":"21","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u00b9\u2077\u2077\u2078)","author":"Joux, Antoine","year":"February 11, 2013"},{"key":"22","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u2076\u00b9\u2076\u2078)","author":"Joux, Antoine","year":"May 21, 2013"},{"key":"23","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u2074\u2070\u2078\u2070)","author":"Joux, Antoine","year":"March 22, 2013"},{"key":"24","doi-asserted-by":"publisher","first-page":"378","article-title":"Improving the polynomial time precomputation of Frobenius representation discrete logarithm algorithms: simplified setting for small characteristic finite fields","author":"Joux, Antoine","year":"2014","DOI":"10.1007\/978-3-662-45611-8_20"},{"key":"25","article-title":"Discrete logarithms in \ud835\udc3a\ud835\udc39(2\u00b9\u00b2\u2077\u2079)","author":"Kleinjung, Thorsten","year":"October 17, 2014"},{"key":"26","doi-asserted-by":"publisher","first-page":"333","article-title":"Factorization of a 768-bit RSA modulus","author":"Kleinjung, Thorsten","year":"2010","DOI":"10.1007\/978-3-642-14623-7_18"},{"key":"27","doi-asserted-by":"publisher","first-page":"358","article-title":"Mersenne factorization factory","author":"Kleinjung, Thorsten","year":"2014","DOI":"10.1007\/978-3-662-45611-8_19"},{"key":"28","doi-asserted-by":"publisher","first-page":"185","article-title":"Computation of a 768-bit prime field discrete logarithm","author":"Kleinjung, Thorsten","year":"2017","DOI":"10.1007\/978-3-319-56620-7_7"},{"key":"29","article-title":"Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic","author":"Kleinjung, Thorsten","year":"June 25, 2019"},{"key":"30","series-title":"LNCS","first-page":"109","article-title":"Solving large sparse linear systems over finite fields","volume":"537","author":"LaMacchia, Brian A.","year":"1991"},{"key":"31","doi-asserted-by":"crossref","first-page":"255","DOI":"10.6028\/jres.045.026","article-title":"An iteration method for the solution of the eigenvalue problem of linear differential and integral operators","volume":"45","author":"Lanczos, Cornelius","year":"1950","journal-title":"J. Research Nat. Bur. Standards","ISSN":"http:\/\/id.crossref.org\/issn\/0160-1741","issn-type":"print"},{"issue":"193","key":"32","doi-asserted-by":"publisher","first-page":"329","DOI":"10.2307\/2008545","article-title":"Finding isomorphisms between finite fields","volume":"56","author":"Lenstra, H. W., Jr.","year":"1991","journal-title":"Math. Comp.","ISSN":"http:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/0000-000-00\/S0025-5718-2021-03669-8\/mcom3669_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/earlyview\/#mcom3669\/.pdf","content-type":"unspecified","content-version":"am","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/0000-000-00\/S0025-5718-2021-03669-8\/S0025-5718-2021-03669-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T18:58:43Z","timestamp":1626461923000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/0000-000-00\/S0025-5718-2021-03669-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,16]]},"references-count":32,"alternative-id":["S0025-5718-2021-03669-8"],"URL":"http:\/\/dx.doi.org\/10.1090\/mcom\/3669","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["0025-5718","1088-6842"],"issn-type":[{"value":"0025-5718","type":"print"},{"value":"1088-6842","type":"electronic"}],"subject":["Applied Mathematics","Computational Mathematics","Algebra and Number Theory"],"published":{"date-parts":[[2021,7,16]]}}}