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