{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:04:54Z","timestamp":1776845094907,"version":"3.51.2"},"reference-count":28,"publisher":"American Mathematical Society (AMS)","issue":"296","license":[{"start":{"date-parts":[[2016,3,20]],"date-time":"2016-03-20T00:00:00Z","timestamp":1458432000000},"content-version":"am","delay-in-days":366,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    The Function Field Sieve algorithm is dedicated to computing discrete logarithms in a finite field\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript q Sub Superscript n\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mi>q<\/mml:mi>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{q^n}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , where\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"q\">\n                        <mml:semantics>\n                          <mml:mi>q<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">q<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is a small prime power. The scope of this article is to select good polynomials for this algorithm by defining and measuring the size property and the so-called root and cancellation properties. In particular we present an algorithm for rapidly testing a large set of polynomials. Our study also explains the behaviour of inseparable polynomials, in particular we give an easy way to see that the algorithm encompass the Coppersmith algorithm as a particular case.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2015-02940-8","type":"journal-article","created":{"date-parts":[[2015,3,20]],"date-time":"2015-03-20T13:32:33Z","timestamp":1426858353000},"page":"2987-3012","source":"Crossref","is-referenced-by-count":4,"title":["Selecting polynomials for the Function Field Sieve"],"prefix":"10.1090","volume":"84","author":[{"given":"Razvan","family":"Barbulescu","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2015,3,20]]},"reference":[{"key":"1","isbn-type":"print","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-58691-1_48","article-title":"The function field sieve","author":"Adleman, Leonard M.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"issue":"1-2","key":"2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1006\/inco.1998.2761","article-title":"Function field sieve method for discrete logarithms over finite fields","volume":"151","author":"Adleman, Leonard M.","year":"1999","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"key":"3","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0999-7","volume-title":"Modular functions and Dirichlet series in number theory","volume":"41","author":"Apostol, Tom M.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0387971270","edition":"2"},{"key":"4","unstructured":"[Bai11] S. Bai, Polynomial selection for the number field sieve, PhD thesis, Australian National University, 2011."},{"key":"5","unstructured":"[BBD{\\etalchar{+}}12] R. Barbulescu, C. Bouvier, J. Detrey, P. Gaudry, H. Jeljeli, E. Thom\u00e9, M. Videau, and P. Zimmermann, The relationship between some guy and cryptography, 2012. Rump session of ECC, http:\/\/ecc.2012.rump.cr.yp.to\/."},{"issue":"3-4","key":"6","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":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"7","unstructured":"[BFG{\\etalchar{+}}] S. Bai, A. Filbois, P. Gaudry, A. Kruppa, F. Morain, E Thom\u00e9, P. Zimmermann, Crible al\u00e9brique: Distribution, optimisation - number field sieve. http:\/\/cado-nfs.gforge.inria.fr\/."},{"key":"8","doi-asserted-by":"crossref","unstructured":"[BGJT13] R. Barbulescu, P. Gaudry, A. Joux, and E. Thom\u00e9, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, \\url{http:\/\/www.springer.com\/computer\/security+and+cryptology\/book\/978-3-642-55219-9}, pp. 1\u201316.","DOI":"10.1007\/978-3-642-55220-5_1"},{"issue":"4","key":"9","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":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[DGV13] J. Detrey, P. Gaudry, and M. Videau, Relation collection for the function field sieve, In IEEE Symposium on Computer Arithmetic (ARITH 21), 2013.","DOI":"10.1109\/ARITH.2013.28"},{"key":"11","unstructured":"[GGMZ13] F. G\u00f6loglu, R. Granger, G. McGuire, and J. Zumbr\u00e4gel, On the function field sieve and the impact of higher splitting probabilities: Application to discrete logarithms in \ud835\udc53_{2\u00b9\u2079\u2077\u00b9}, \\url{http:\/\/www.springer.com\/computer\/security+and+cryptology\/book\/978-3-642-40083-4}."},{"key":"12","series-title":"Graduate Texts in Mathematics, No. 52","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3849-0","volume-title":"Algebraic geometry","author":"Hartshorne, Robin","year":"1977","ISBN":"https:\/\/id.crossref.org\/isbn\/0387902449"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[HSST12] T. Hayashi, T. Shimoyama, N. Shinohara, and T. Takagi, Breaking pairing-based cryptosystems using \ud835\udf02_{\ud835\udc61} pairing over \ud835\udc3a\ud835\udc39(3\u2079\u2077). In Advances in Cryptology \u2013 ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 43\u201360, 2012.","DOI":"10.1007\/978-3-642-34961-4_5"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-13013-7_21","article-title":"Solving a 676-bit discrete logarithm problem in \ud835\udc3a\ud835\udc39(3\u2076\u207f)","author":"Hayashi, Takuya","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642130120"},{"key":"15","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2103-4","volume-title":"A classical introduction to modern number theory","volume":"84","author":"Ireland, Kenneth","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/038797329X","edition":"2"},{"key":"16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/3-540-45455-1_34","article-title":"The function field sieve is quite special","author":"Joux, Antoine","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540438637"},{"issue":"242","key":"17","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1090\/S0025-5718-02-01482-5","article-title":"Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method","volume":"72","author":"Joux, Antoine","year":"2003","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11761679_16","article-title":"The function field sieve in the medium prime case","author":"Joux, Antoine","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540345466"},{"key":"19","unstructured":"[JL07] A. Joux and R. Lercier, 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, page 23, 2007."},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-38348-9_11","article-title":"Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields","author":"Joux, Antoine","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642383489"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[Jou13b] A. Joux, A new index calculus algorithm with complexity L(1\/4+\ud835\udc5c(1)) in very small characteristic. Cryptology ePrint Archive, Report 2013\/095, 2013. http:\/\/eprint.iacr.org\/.","DOI":"10.1007\/978-3-662-43414-7_18"},{"key":"22","series-title":"Graduate Studies in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/009","volume-title":"An invitation to arithmetic geometry","volume":"9","author":"Lorenzini, Dino","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0821802674"},{"key":"23","unstructured":"[Mat99] R. Matsumoto, Using Cab curves in the function field sieve. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 82(3):551\u2013552, 1999."},{"key":"24","unstructured":"[Mon06] P.L. Montgomery, Searching for higher-degree polynomials for the general number field sieve, 2006. http:\/\/www.ipam.ucla.edu\/publications\/scws1\/scws1_6223.ppt."},{"key":"25","unstructured":"[Mur99] B.A. Murphy, Polynomial selection for the number field sieve integer factorisation algorithm, PhD thesis, Australian National University, 1999."},{"key":"26","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03983-0","volume-title":"Algebraic number theory","volume":"322","author":"Neukirch, J\u00fcrgen","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540653996"},{"issue":"4","key":"27","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.jsc.2011.09.004","article-title":"Non-linear polynomial selection for the number field sieve","volume":"47","author":"Prest, Thomas","year":"2012","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"28","unstructured":"[Tho03] E. Thom\u00e9. Algorithmes de calcul des logarithmes discrets dans les corps finis, PhD thesis, \u00c9cole Polytechnique, Palaiseau, France, 2003."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02940-8\/S0025-5718-2015-02940-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02940-8\/S0025-5718-2015-02940-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:33:33Z","timestamp":1776796413000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2015-84-296\/S0025-5718-2015-02940-8\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,20]]},"references-count":28,"journal-issue":{"issue":"296","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["S0025-5718-2015-02940-8"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2015-02940-8","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2015,3,20]]}}}