{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T08:53:49Z","timestamp":1776848029010,"version":"3.51.2"},"reference-count":39,"publisher":"American Mathematical Society (AMS)","issue":"223","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n over a finite field of constant cardinality in time\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1.815<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O(n^{1.815})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . Previous algorithms required time\n \n \n \n \n \n \u0398\n \n <\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 2<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Theta (n^{2+o(1)})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n over the finite field\n \n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n q<\/mml:mi>\n <\/mml:msub>\n {\\mathbb F}_q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with\n \n \n \n q<\/mml:mi>\n q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n elements, the algorithms use\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 1.815<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n q<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n O(n^{1.815} \\log q)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n arithmetic operations in\n \n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n q<\/mml:mi>\n <\/mml:msub>\n {\\mathbb F}_q<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . The new \u201cbaby step\/giant step\u201d techniques used in our algorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-time methods for manipulating normal bases of finite fields.\n <\/p>","DOI":"10.1090\/s0025-5718-98-00944-2","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1179-1197","source":"Crossref","is-referenced-by-count":94,"title":["Subquadratic-time factoring of polynomials over finite fields"],"prefix":"10.1090","volume":"67","author":[{"given":"Erich","family":"Kaltofen","sequence":"first","affiliation":[]},{"given":"Victor","family":"Shoup","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","series-title":"Addison-Wesley Series in Computer Science and Information Processing","volume-title":"The design and analysis of computer algorithms","author":"Aho, Alfred V.","year":"1975"},{"issue":"3","key":"2","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","article-title":"The complexity of partial derivatives","volume":"22","author":"Baur, Walter","year":"1983","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Probabilistic algorithms in finite fields, Proc. 22nd IEEE Symp. Foundations Comp. Sci., 394\u2013398, 1981.","DOI":"10.1109\/SFCS.1981.37"},{"key":"4","doi-asserted-by":"publisher","first-page":"713","DOI":"10.2307\/2004849","article-title":"Factoring polynomials over large finite fields","volume":"24","author":"Berlekamp, E. R.","year":"1970","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"5","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0196-6774(80)90013-9","article-title":"Fast solution of Toeplitz systems of equations and computation of Pad\u00e9 approximants","volume":"1","author":"Brent, Richard P.","year":"1980","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"issue":"4","key":"6","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1145\/322092.322099","article-title":"Fast algorithms for manipulating formal power series","volume":"25","author":"Brent, R. P.","year":"1978","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Canny, J., Kaltofen, E. and Lakshman Yagati, Solving systems of non-linear polynomial equations faster, Proc. ACM-SIGSAM 1989 Internat. Symp. Symbolic Algebraic Comput., 121\u2013128, ACM Press, 1989.","DOI":"10.1145\/74540.74556"},{"issue":"7","key":"8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/BF01178683","article-title":"On fast multiplication of polynomials over arbitrary algebras","volume":"28","author":"Cantor, David G.","year":"1991","journal-title":"Acta Inform.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5903","issn-type":"print"},{"issue":"154","key":"9","doi-asserted-by":"publisher","first-page":"587","DOI":"10.2307\/2007663","article-title":"A new algorithm for factoring polynomials over finite fields","volume":"36","author":"Cantor, David G.","year":"1981","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"3","key":"10","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0211037","article-title":"Rapid multiplication of rectangular matrices","volume":"11","author":"Coppersmith, D.","year":"1982","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"issue":"3","key":"11","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith, Don","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1109\/TIT.1987.1057299","article-title":"On the equivalence between Berlekamp\u2019s and Euclid\u2019s algorithms","volume":"33","author":"Dornstetter, Jean-Louis","year":"1987","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"13","first-page":"31","article-title":"On obtaining upper bounds on the complexity of matrix multiplication","author":"Fiduccia, Charles M.","year":"1972"},{"key":"14","unstructured":"Fiduccia, C. M., On the Algebraic Complexity of Matrix Multiplication, Ph.D. Thesis, Center Comput. Inform. Sci., Div. Engin., Brown Univ., Providence, Rhode Island, June 1973."},{"key":"15","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(93)90238-J","article-title":"Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \ud835\udc39_{\ud835\udc5e}","volume":"192","author":"Fleischmann, Peter","year":"1993","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"6","key":"16","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/S0747-7171(08)80158-7","article-title":"Constructing normal bases in finite fields","volume":"10","author":"von zur Gathen, Joachim","year":"1990","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/BF01272074","article-title":"Computing Frobenius maps and factoring polynomials","volume":"2","author":"von zur Gathen, Joachim","year":"1992","journal-title":"Comput. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/1016-3328","issn-type":"print"},{"key":"18","unstructured":"Giesbrecht, M., Nearly optimal algorithms for canonical matrix forms, Ph.D. Thesis, Dept. Comput. Science, University of Toronto, Toronto, Canada, 1993."},{"key":"19","doi-asserted-by":"crossref","unstructured":"Griewank, A., Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation, Optimization Methods and Software, Gordon and Breach Science Publishers, vol. 1, 35\u201354, 1992.","DOI":"10.1080\/10556789208805505"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., and Lobo, A., Factoring high-degree polynomials by the black box Berlekamp algorithm, Proc. Internat. Symp. Symbolic Algebraic Comput. ISSAC \u201994, (J. von zur Gathen and M. Giesbrecht), ACM Press, New York, N. Y., 90\u201398, 1994.","DOI":"10.1145\/190347.190371"},{"key":"21","doi-asserted-by":"crossref","unstructured":"Kaltofen, E., and Pan, V., Processor efficient parallel solution of linear systems over an abstract field, Proc. 3rd Ann. ACM Symp. Parallel Algor. Architecture, ACM Press, 1991, 180\u2013191.","DOI":"10.1145\/113379.113396"},{"issue":"3","key":"22","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/0196-6774(88)90026-0","article-title":"Addition requirements for matrix and transposed matrix products","volume":"9","author":"Kaminski, Michael","year":"1988","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"23","series-title":"Addison-Wesley Series in Computer Science and Information Processing","isbn-type":"print","volume-title":"The art of computer programming. Vol. 2","author":"Knuth, Donald E.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201038226","edition":"2"},{"key":"24","series-title":"Encyclopedia of Mathematics and its Applications","isbn-type":"print","volume-title":"Finite fields","volume":"20","author":"Lidl, Rudolf","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0201135191"},{"issue":"2","key":"25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/bf01931367","article-title":"Taylor expansion of the accumulated rounding error","volume":"16","author":"Linnainmaa, Seppo","year":"1976","journal-title":"Nordisk Tidskr. Informationsbehandling (BIT)","ISSN":"https:\/\/id.crossref.org\/issn\/0901-246X","issn-type":"print"},{"issue":"2","key":"26","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0304-3975(83)90054-3","article-title":"On the asymptotic complexity of rectangular matrix multiplication","volume":"23","author":"Lotti, Grazia","year":"1983","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"27","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1109\/tit.1969.1054260","article-title":"Shift-register synthesis and BCH decoding","volume":"IT-15","author":"Massey, James L.","year":"1969","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"28","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF01386831","article-title":"A new efficient factorization algorithm for polynomials over small finite fields","volume":"4","author":"Niederreiter, Harald","year":"1993","journal-title":"Appl. Algebra Engrg. Comm. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0938-1279","issn-type":"print"},{"issue":"5","key":"29","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1006\/jsco.1993.1055","article-title":"Factorization of polynomials over finite fields and characteristic sequences","volume":"16","author":"Niederreiter, Harald","year":"1993","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"30","unstructured":"Ostrowski, G. M., Wolin, Ju. M. and Borisow, W. W., \u00dcber die Berechnung von Ableitungen, Wissenschaftliche Zeitschrift Techn. Hochsch. Chem. Leuna-Merseburg, vol. 13, no. 4, 382\u2013384, 1971."},{"issue":"2","key":"31","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0209024","article-title":"Probabilistic algorithms in finite fields","volume":"9","author":"Rabin, Michael O.","year":"1980","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"32","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1093\/qmath\/7.1.110","article-title":"On the reducibility of polynomials over a finite field","volume":"7","author":"Schwarz, \u0160tefan","year":"1956","journal-title":"Quart. J. Math. Oxford Ser. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"issue":"5","key":"33","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(90)90195-4","article-title":"On the deterministic complexity of factoring polynomials over finite fields","volume":"33","author":"Shoup, Victor","year":"1990","journal-title":"Inform. Process. Lett.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-0190","issn-type":"print"},{"issue":"5","key":"34","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1006\/jsco.1994.1025","article-title":"Fast construction of irreducible polynomials over finite fields","volume":"17","author":"Shoup, Victor","year":"1994","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"4","key":"35","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1006\/jsco.1995.1055","article-title":"A new polynomial factorization algorithm and its implementation","volume":"20","author":"Shoup, Victor","year":"1995","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"1","key":"36","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"32","author":"Wiedemann, Douglas H.","year":"1986","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"37","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, Springer-Verlag, Heidelberg, Germany, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"38","doi-asserted-by":"crossref","unstructured":"Huang, X. and Pan, V., Fast rectangular matrix multiplications and improving parallel matrix computations, In Proc. Second Internat. Symp. Parallel Symbolic Comput. PASCO \u201997, M. Hitz and E. Kaltofen, editors, pages 11\u201323, New York, N.Y., 1997. ACM Press.","DOI":"10.1145\/266670.266679"},{"key":"39","doi-asserted-by":"crossref","unstructured":"Kaltofen, E. and Shoup, V., Fast polynomial factorization over high algebraic extensions of finite fields. In ISSAC 97 Proc. 1997 Internat. Symp. Symbolic Algebraic Comput., W. K\u00fcchlin, editor, pages 184\u2013188, New York, N.Y., 1997. ACM Press.","DOI":"10.1145\/258726.258777"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00944-2\/S0025-5718-98-00944-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00944-2\/S0025-5718-98-00944-2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:30Z","timestamp":1776721710000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00944-2\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":39,"journal-issue":{"issue":"223","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0025-5718-98-00944-2"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00944-2","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":[[1998]]}}}