{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:48:00Z","timestamp":1776728880976,"version":"3.51.2"},"reference-count":20,"publisher":"American Mathematical Society (AMS)","issue":"244","license":[{"start":{"date-parts":[[2004,4,21]],"date-time":"2004-04-21T00:00:00Z","timestamp":1082505600000},"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>The most time-consuming part of the Niederreiter algorithm for factoring univariate polynomials over finite fields is the computation of elements of the nullspace of a certain matrix. This paper describes the so-called \u201cblack-box\u201d Niederreiter algorithm, in which these elements are found by using a method developed by Wiedemann. The main advantages over an approach based on Gaussian elimination are that the matrix does not have to be stored in memory and that the computational complexity of this approach is lower. The black-box Niederreiter algorithm for factoring polynomials over the binary field was implemented in the C programming language, and benchmarks for factoring high-degree polynomials over this field are presented. These benchmarks include timings for both a sequential implementation and a parallel implementation running on a small cluster of workstations. In addition, the Wan algorithm, which was recently introduced, is described, and connections between (implementation aspects of) Wan\u2019s and Niederreiter\u2019s algorithm are given.<\/p>","DOI":"10.1090\/s0025-5718-03-01494-7","type":"journal-article","created":{"date-parts":[[2003,6,20]],"date-time":"2003-06-20T10:23:27Z","timestamp":1056104607000},"page":"1887-1899","source":"Crossref","is-referenced-by-count":4,"title":["The black-box Niederreiter algorithm and its implementation over the binary field"],"prefix":"10.1090","volume":"72","author":[{"given":"Peter","family":"Fleischmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Roelse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2003,4,21]]},"reference":[{"key":"1","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"},{"issue":"2","key":"2","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":"154","key":"3","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":"4","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"},{"key":"5","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":"6","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":"7","series-title":"Vorlesungen aus dem Fachbereich Mathematik der Universit\\\"{a}t GH Essen [Lecture Notes in Mathematics at the University of Essen]","volume-title":"Arithmetik grossgradiger Polynome \\\"{u}ber kleinen endlichen K\\\"{o}rpern","volume":"28","author":"Holder, Markus Chr.","year":"2000"},{"key":"8","doi-asserted-by":"crossref","unstructured":"E. Kaltofen and A. Lobo, Factoring high\u2013degree polynomials by the black box Berlekamp algorithm, ISSAC \u201994 (J. von zur Gathen and M. Giesbrecht, eds.), 1994, pp. 90\u201398.","DOI":"10.1145\/190347.190371"},{"key":"9","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54522-0","volume-title":"Applied algebra, algebraic algorithms and error-correcting codes","volume":"539","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/3540545220"},{"issue":"223","key":"10","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":"11","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"},{"key":"12","series-title":"Springer Series in Discrete Mathematics and Theoretical Computer Science","isbn-type":"print","volume-title":"Polynomials","author":"Mignotte, Maurice","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/9814021512"},{"issue":"2","key":"13","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"},{"key":"14","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"},{"issue":"5","key":"15","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":"16","series-title":"Vorlesungen aus dem Fachbereich Mathematik der Universit\\\"{a}t GH Essen [Lecture Notes in Mathematics at the University of Essen]","volume-title":"Linear methods for polynomial factorization over finite fields","volume":"25","author":"Roelse, Peter L. A.","year":"1997"},{"issue":"226","key":"17","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"},{"key":"18","isbn-type":"print","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1090\/conm\/225\/03215","article-title":"Computing zeta functions over finite fields","author":"Wan, Daqing","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0821808176"},{"issue":"1","key":"19","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":"20","doi-asserted-by":"crossref","unstructured":"D.Y.Y. Yun, On square-free decomposition algorithms, Proc. ACM Symp. Symbolic and Algebraic Comput. (R.D. Jenks, ed.), 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\/2003-72-244\/S0025-5718-03-01494-7\/S0025-5718-03-01494-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-244\/S0025-5718-03-01494-7\/S0025-5718-03-01494-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:25:41Z","timestamp":1776727541000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2003-72-244\/S0025-5718-03-01494-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4,21]]},"references-count":20,"journal-issue":{"issue":"244","published-print":{"date-parts":[[2003,10]]}},"alternative-id":["S0025-5718-03-01494-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-03-01494-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":[[2003,4,21]]}}}