## Factoring high-degree polynomials over $\mathbf F_2$ with Niederreiterâs algorithm on the IBM SP2

HTML articles powered by AMS MathViewer

- by Peter Roelse PDF
- Math. Comp.
**68**(1999), 869-880 Request permission

## Abstract:

A $C$ implementation of Niederreiterâs algorithm for factoring polynomials over ${\mathbf F}_2$ is described. The most time-consuming part of this algorithm, which consists of setting up and solving a certain system of linear equations, is performed in parallel. Once a basis for the solution space is found, all irreducible factors of the polynomial can be extracted by suitable $\gcd$-computations. For this purpose, asymptotically fast polynomial arithmetic algorithms are implemented. These include Karatsuba & Ofman multiplication, Cantor multiplication and Newton inversion. In addition, a new efficient version of the half-gcd algorithm is presented. Sequential run times for the polynomial arithmetic and parallel run times for the factorization are given. A new âworld recordâ for polynomial factorization over the binary field is set by showing that a pseudo-randomly selected polynomial of degree 300000 can be factored in about 10 hours on 256 nodes of the IBM SP2 at the Cornell Theory Center.## References

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,
*The design and analysis of computer algorithms*, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR**0413592** - Eric Bach and Jeffrey Shallit,
*Algorithmic number theory. Vol. 1*, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR**1406794** - David G. Cantor,
*On arithmetical algorithms over finite fields*, J. Combin. Theory Ser. A**50**(1989), no.Â 2, 285â300. MR**989199**, DOI 10.1016/0097-3165(89)90020-4 - K. Dowd,
*High Performance Computing*, OâReilly & Associates Inc., 1993. - A. Diaz, E. Kaltofen and V. Pan,
*Algebraic algorithms*, The Computer Science and Engineering Handbook (A.B. Tucker, ed.), CRC Press, 1997, pp. 226â249. - Peter Fleischmann and Peter Roelse,
*Comparative implementations of Berlekampâs and Niederreiterâs polynomial factorization algorithms*, Finite fields and applications (Glasgow, 1995) London Math. Soc. Lecture Note Ser., vol. 233, Cambridge Univ. Press, Cambridge, 1996, pp.Â 73â83. MR**1433141**, DOI 10.1017/CBO9780511525988.009 - J. von zur Gathen and J. Gerhard,
*Arithmetic and factorization of polynomials over $F_2$*, Proc. ISSAC â96, ACM Press, 1996, pp. 1-9. - K. O. Geddes, S. R. Czapor, and G. Labahn,
*Algorithms for computer algebra*, Kluwer Academic Publishers, Boston, MA, 1992. MR**1256483**, DOI 10.1007/b102438 - J. Gerhard,
*Faktorisieren von Polynomen Ăźber $\textbf {F}_q$: ein Vergleich neuerer Verfahren*, Masterâs thesis, University of Erlangen-NĂźrnberg, 1994. - IBM,
*AIX Version 3.2 for RISC System/6000: Optimization and Tuning Guide for Fortran, C, and C++*, IBM Manual, 1993. - E. Kaltofen and A. Lobo,
*Factoring high-degree polynomials by the black box Berlekamp algorithm*, Proc. ISSAC â94 (J. von zur Gathen and M. Giesbrecht, eds.), ACM Press, 1994, pp. 90â98. - A. Karatsuba and Y. Ofman,
*Multiplication of multidigit numbers on automata*, Soviet Phys. Dokl.**7**(1963), 595â596. - Harald Niederreiter,
*New deterministic factorization algorithms for polynomials over finite fields*, Finite fields: theory, applications, and algorithms (Las Vegas, NV, 1993) Contemp. Math., vol. 168, Amer. Math. Soc., Providence, RI, 1994, pp.Â 251â268. MR**1291434**, DOI 10.1090/conm/168/01705 - D. Reischert,
*Schnelle Multiplikation von Polynomen Ăźber $GF(2)$ und Anwendungen*, Masterâs thesis, University of Bonn, 1995. - D. Reischert,
*Multiplication by a Square is cheap over $F_2$*, Preprint, 1996. - Victor Shoup,
*A new polynomial factorization algorithm and its implementation*, J. Symbolic Comput.**20**(1995), no.Â 4, 363â397. MR**1384454**, DOI 10.1006/jsco.1995.1055 - V. Strassen,
*The computational complexity of continued fractions*, SIAM J. Comput.**12**(1983), no.Â 1, 1â27. MR**687799**, DOI 10.1137/0212001 - M. Weller,
*Parallel Gaussian elimination over small finite fields*, Parallel and Distributed Computing Systems, Proc. of the ISCA International Conference (K. Yetongnon and S. Hariri, eds.), 1996, 56â63. - D.Y.Y. Yun,
*On square-free decomposition algorithms*, Proc. ACM Symp. Symbolic and Algebraic Comput. (R.D. Jenks, ed.), 1976, pp. 26â35.

## Additional Information

**Peter Roelse**- Affiliation: Institute for Experimental Mathematics, University of Essen, Ellernstrasse 29, 45326 Essen, Germany
- Address at time of publication: Philips Crypto B.V., De Witbogt 2, 5652 AG Eindhoven, The Netherlands
- Email: roelse@exp-math.uni-essen.de, roelse@crypto.philips.com
- Received by editor(s): May 19, 1997
- Received by editor(s) in revised form: August 11, 1997
- © Copyright 1999 American Mathematical Society
- Journal: Math. Comp.
**68**(1999), 869-880 - MSC (1991): Primary 11--04, 11T06, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-99-01008-X
- MathSciNet review: 1604383