{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:40:37Z","timestamp":1776728437572,"version":"3.51.2"},"reference-count":38,"publisher":"American Mathematical Society (AMS)","issue":"240","license":[{"start":{"date-parts":[[2003,5,3]],"date-time":"2003-05-03T00:00:00Z","timestamp":1051920000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We describe algorithms for polynomial factorization over the binary 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 2\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">{\\mathbb F}_2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    , and their implementation. They allow polynomials of degree up to\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"250 000\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mn>250<\/mml:mn>\n                            <mml:mspace width=\"thinmathspace\"\/>\n                            <mml:mn>000<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">250\\,000<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    to be factored in about one day of CPU time, distributing the work on two processors.\n                  <\/p>","DOI":"10.1090\/s0025-5718-02-01421-7","type":"journal-article","created":{"date-parts":[[2002,9,20]],"date-time":"2002-09-20T14:12:48Z","timestamp":1032531168000},"page":"1677-1698","source":"Crossref","is-referenced-by-count":10,"title":["Polynomial factorization over \ud835\udd3d\u2082"],"prefix":"10.1090","volume":"71","author":[{"given":"Joachim","family":"von zur Gathen","sequence":"first","affiliation":[]},{"given":"J\u00fcrgen","family":"Gerhard","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2002,5,3]]},"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"},{"key":"2","unstructured":"A. Arwin, \u00dcber Kongruenzen von dem f\u00fcnften und h\u00f6heren Graden nach einem Primzahlmodulus, Ark. Mat. 14 (1918), no. 7, 1\u201346."},{"key":"3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Probabilistic algorithms in finite fields, Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science,  Nashville TN, 1981, pp. 394\u2013398.","DOI":"10.1109\/SFCS.1981.37"},{"key":"4","doi-asserted-by":"publisher","first-page":"1853","DOI":"10.1002\/j.1538-7305.1967.tb03174.x","article-title":"Factoring polynomials over finite fields","volume":"46","author":"Berlekamp, E. R.","year":"1967","journal-title":"Bell System Tech. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0005-8580","issn-type":"print"},{"key":"5","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"},{"key":"6","volume-title":"Algebraic coding theory","author":"Berlekamp, Elwyn R.","year":"1968"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Olaf Bonorden, Joachim von zur Gathen, J\u00fcrgen Gerhard, Olaf M\u00fcller, and Michael N\u00f6cker, Factoring a binary polynomial of degree over one million, ACM SIGSAM Bull. 35 (1), 2001, 16\u201318.","DOI":"10.1145\/504331.504333"},{"issue":"2","key":"8","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/0097-3165(89)90020-4","article-title":"On arithmetical algorithms over finite fields","volume":"50","author":"Cantor, David G.","year":"1989","journal-title":"J. Combin. Theory Ser. A","ISSN":"https:\/\/id.crossref.org\/issn\/0097-3165","issn-type":"print"},{"issue":"7","key":"9","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":"10","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"},{"key":"11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-61440-0_131","article-title":"Random polynomials and polynomial factorization","author":"Flajolet, Philippe","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/3540614400"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1017\/CBO9780511525988.009","article-title":"Comparative implementations of Berlekamp\u2019s and Niederreiter\u2019s polynomial factorization algorithms","author":"Fleischmann, Peter","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/052156736X"},{"key":"13","volume-title":"Ecrits et m\\'{e}moires math\\'{e}matiques d'\\'{E}variste Galois: \\'{E}dition critique int\\'{e}grale de ses manuscrits et publications","author":"Bourgne, Robert","year":"1962"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1090\/conm\/168\/01691","article-title":"Berlekamp\u2019s and Niederreiter\u2019s polynomial factorization algorithms","author":"Gao, Shuhong","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821851837"},{"key":"15","unstructured":"Joachim von zur Gathen and J\u00fcrgen Gerhard, Arithmetic and factorization of polynomials over \u2124\u2082, Tech. Report tr-rsfb-96-018, University of Paderborn, Germany, 1996, 43 pages."},{"key":"16","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"key":"17","unstructured":"Joachim von zur Gathen, X. Gourdon, and D. Panario, Average cost of baby-step\/giant-step polynomial factorization algorithms, in preparation, 2002."},{"key":"18","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen and Daniel Panario, Factoring polynomials over finite fields: A survey, J. Symbolic Comput. 31 (2001), no. 1\u20132, 3\u201317.","DOI":"10.1006\/jsco.1999.1002"},{"issue":"3","key":"19","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"},{"issue":"2","key":"20","first-page":"90","article-title":"\u0100ryabha\u1e6da\u2019s contribution to Indian astronomy","volume":"12","author":"Sharma, M. L.","year":"1977","journal-title":"Indian J. Hist. Sci."},{"key":"21","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023811","volume-title":"LATIN '92","volume":"583","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/3540552847"},{"key":"22","doi-asserted-by":"crossref","unstructured":"E. Kaltofen and A. Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation ISSAC \u201994, Oxford, UK (J. von zur Gathen and M. Giesbrecht, eds.), ACM Press, 1994, pp. 90\u201398.","DOI":"10.1145\/190347.190371"},{"issue":"6","key":"23","first-page":"571","article-title":"Deduction properties of some logics applied to computer science","volume":"22","author":"Zhang, Yu Ping","year":"1999","journal-title":"Chinese J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0254-4164","issn-type":"print"},{"issue":"223","key":"24","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1090\/S0025-5718-98-00944-2","article-title":"Subquadratic-time factoring of polynomials over finite fields","volume":"67","author":"Kaltofen, Erich","year":"1998","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"25","unstructured":"A. Karatsuba and Yu. Ofman, Umnozhenie mnogoznachnykh chisel na avtomatakh, Doklady Akademi\u012d Nauk SSSR 145 (1962), 293\u2013294. A. Karatsuba and Yu. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics\u2013Doklady 7 (1963), 595\u2013596."},{"issue":"1-3","key":"26","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0012-365X(93)90227-K","article-title":"Counting irreducible factors of polynomials over a finite field","volume":"112","author":"Knopfmacher, Arnold","year":"1993","journal-title":"Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0012-365X","issn-type":"print"},{"key":"27","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"},{"key":"28","unstructured":"Peter L. Montgomery, Factorization of \ud835\udc4b\u00b2\u00b9\u2076\u2070\u2079\u00b9+\ud835\udc4b+1\\bmod2\u2014A problem of Herb Doughty, manuscript, February 1991."},{"key":"29","isbn-type":"print","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1090\/conm\/168\/01705","article-title":"New deterministic factorization algorithms for polynomials over finite fields","author":"Niederreiter, Harald","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0821851837"},{"key":"30","unstructured":"Daniel Reischert, Schnelle Multiplikation von Polynomen \u00fcber GF(2) und Anwendungen, Diplomarbeit, Institut f\u00fcr Informatik II, Rheinische Friedrich-Wilhelm-Universit\u00e4t Bonn, Germany, August 1995."},{"key":"31","unstructured":"\\bysame, Multiplication by a square is cheap over \ud835\udd3d\u2082, manuscript, 1996."},{"issue":"226","key":"32","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1090\/S0025-5718-99-01008-X","article-title":"Factoring high-degree polynomials over \ud835\udc39\u2082 with Niederreiter\u2019s algorithm on the IBM SP2","volume":"68","author":"Roelse, Peter","year":"1999","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"33","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/bf00289470","article-title":"Schnelle Multiplikation von Polynomen \u00fcber K\u00f6rpern der Charakteristik 2","volume":"7","author":"Sch\u00f6nhage, A.","year":"1976","journal-title":"Acta Informat."},{"key":"34","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"35","unstructured":"J.-A. Serret, Cours d\u2019alg\u00e8bre sup\u00e9rieure, 3rd ed., Gauthier-Villars, Paris, 1866."},{"issue":"4","key":"36","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":"37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0212001","article-title":"The computational complexity of continued fractions","volume":"12","author":"Strassen, V.","year":"1983","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"38","doi-asserted-by":"crossref","unstructured":"David Y. Y. Yun, On square-free decomposition algorithms, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC \u201976, Yorktown Heights NY (R. D. Jenks, ed.), ACM Press, 1976, pp. 26\u201335.","DOI":"10.1145\/800205.806320"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-02-01421-7\/S0025-5718-02-01421-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-02-01421-7\/S0025-5718-02-01421-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:04:19Z","timestamp":1776726259000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2002-71-240\/S0025-5718-02-01421-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,5,3]]},"references-count":38,"journal-issue":{"issue":"240","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0025-5718-02-01421-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-02-01421-7","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":[[2002,5,3]]}}}