Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Subquadratic-time factoring of polynomials
over finite fields

Authors: Erich Kaltofen and Victor Shoup
Journal: Math. Comp. 67 (1998), 1179-1197
MSC (1991): Primary 12E20, 13P05, 68Q40
MathSciNet review: 1459389
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree $n$ over a finite field of constant cardinality in time $O(n^{1.815})$. Previous algorithms required time $\Theta(n^{2+o(1)})$. The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree $n$ over the finite field ${\mathbb F}_q$ with $q$ elements, the algorithms use $O(n^{1.815} \log q)$ arithmetic operations in ${\mathbb F}_q$.

The new ``baby step/giant step'' 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.

References [Enhancements On Off] (What's this?)

  • 1. Aho, A., Hopcroft, J. and Ullman, J., Design and Analysis of Computer Algorithms, Addison and Wesley, Reading, MA, 1974. MR 54:1706
  • 2. Baur, W. and Strassen, V., The complexity of partial derivatives, Theoretical Comp. Sci., vol. 22, 317-330, 1983. MR 84c:68027
  • 3. Ben-Or, M., Probabilistic algorithms in finite fields, Proc. 22nd IEEE Symp. Foundations Comp. Sci., 394-398, 1981.
  • 4. Berlekamp, E. R., Factoring polynomials over large finite fields, Math. Comp., 24, 1970, 713-735. MR 43:1948
  • 5. Brent, R. P., Gustavson, F. G., and Yun, D. Y. Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, vol. 1, 259-295, 1980. MR 82d:65033
  • 6. Brent, R. P. and Kung, H. T., Fast algorithms for manipulating formal power series, J. ACM, vol. 25, no. 4, 581-595, 1978. MR 58:25090
  • 7. 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-128, ACM Press, 1989.
  • 8. Cantor, D. G. and Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Inform., vol. 28, no. 7, 693-701, 1991. MR 92i:68068
  • 9. Cantor, D. G. and Zassenhaus, H., A new algorithm for factoring polynomials over finite fields, Math. Comp., vol. 36, 587-592, 1981. MR 82e:12020
  • 10. Coppersmith, D., Rapid multiplication of rectangular matrices, SIAM J. Comput., vol. 11, no. 3, 467-471, 1982. MR 83j:68047a
  • 11. Coppersmith, D. and Winograd, S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput., vol. 9, no. 3, 251-280, 1990. MR 91i:68058
  • 12. Dornstetter, J. L., On the equivalence between Berlekamp's and Euclid's algorithms, IEEE Trans. Inf. Theory, vol. 33, no. 3, 428-431, 1987. MR 88j:94018
  • 13. Fiduccia, C. M., On obtaining upper bounds on the complexity of matrix multiplication, Complexity of Computer Computations, (R. E. Miller and J. W. Thatcher), Plenum Press, New York, 1972, 31-40. MR 52:12398
  • 14. 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.
  • 15. Fleischmann, P., Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over ${\mathbb F}_{\!q}$, Linear Algebra and Applications, vol. 192, 101-108, 1993. MR 94f:11129
  • 16. von zur Gathen, J., and Giesbrecht, M., Constructing normal bases in finite fields, J. Symbolic Comput., vol. 10, no. 6, 547-570, 1990. MR 92e:11142
  • 17. von zur Gathen, J., and Shoup, V., Computing Frobenius maps and factoring polynomials, Comput. Complexity, vol. 2, 187-224, 1992. MR 94d:12011
  • 18. Giesbrecht, M., Nearly optimal algorithms for canonical matrix forms, Ph.D. Thesis, Dept. Comput. Science, University of Toronto, Toronto, Canada, 1993.
  • 19. 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-54, 1992.
  • 20. Kaltofen, E., and Lobo, A., Factoring high-degree polynomials by the black box Berlekamp algorithm, Proc. Internat. Symp. Symbolic Algebraic Comput. ISSAC '94, (J. von zur Gathen and M. Giesbrecht), ACM Press, New York, N. Y., 90-98, 1994.
  • 21. 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-191.
  • 22. Kaminski, M., Kirkpatrick, D. G. and Bshouty, N. H., Addition requirements for matrix and transposed matrix products, J. Algorithms, vol. 9, 354-364, 1988. MR 89m:68061
  • 23. Knuth, D. E., The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Ed. 2, Addison Wesley, Reading, MA, 1981. MR 83i:68003
  • 24. Lidl, R. and Niederreiter, H., Finite Fields, Addison-Wesley, Reading, MA, 1983. MR 86c:11106
  • 25. Linnainmaa, S., Taylor expansion of the accumulated rounding error, BIT, vol. 16, 146-160, 1976. MR 54:9070
  • 26. Lotti, G., and Romani, F., On the asymptotic complexity of rectangular matrix multiplication, Theoretical Comput. Sci.,, vol. 23, 171-185, 1983. MR 84g:68029
  • 27. Massey, J. L., Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, vol. 15, 122-127, 1969. MR 39:3887
  • 28. Niederreiter, H., A new efficient factorization algorithm for polynomials over small finite fields, Applic. Algebra Engin., Commun. Comput., vol. 4, 81-87, 1993. MR 94h:11112
  • 29. Niederreiter, H. and Göttfert, R., Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput., vol. 16, no. 5, 401-412, 1993. MR 95d:68072
  • 30. Ostrowski, G. M., Wolin, Ju. M. and Borisow, W. W., Über die Berechnung von Ableitungen, Wissenschaftliche Zeitschrift Techn. Hochsch. Chem. Leuna-Merseburg, vol. 13, no. 4, 382-384, 1971.
  • 31. Rabin, M. O., Probabilistic algorithms in finite fields, SIAM J. Comp., vol. 9, 273-280, 1980. MR 81g:12002
  • 32. Schwarz, \v{S}t., On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2), vol. 7, 110-124, 1956. MR 20:3162
  • 33. Shoup, V., On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Letters, vol. 33, no. 5, 261-267, 1990. MR 91f:11088
  • 34. Shoup, V., Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput., vol. 17, no. 5, 371-391, 1994. MR 95k:11156
  • 35. Shoup, V., A new polynomial factorization algorithm and its implementation, J. Symbolic Comput., vol. 20, 363-397, 1995. MR 97d:12011
  • 36. Wiedemann, D., Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory, vol. 32, 54-62, 1986. MR 87g:11166
  • 37. Bürgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, Springer-Verlag, Heidelberg, Germany, 1997. CMP 97:10
  • 38. Huang, X. and Pan, V., Fast rectangular matrix multiplications and improving parallel matrix computations, In Proc. Second Internat. Symp. Parallel Symbolic Comput. PASCO '97, M. Hitz and E. Kaltofen, editors, pages 11-23, New York, N.Y., 1997. ACM Press.
  • 39. 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üchlin, editor, pages 184-188, New York, N.Y., 1997. ACM Press.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 12E20, 13P05, 68Q40

Retrieve articles in all journals with MSC (1991): 12E20, 13P05, 68Q40

Additional Information

Erich Kaltofen
Affiliation: Department of Mathematics, North Carolina State University, Raleigh, North Carolina 27695-8205

Victor Shoup
Affiliation: Bellcore, 445 South St., Morristown, New Jersey 07960-6438
Address at time of publication: IBM Zurich Research Laboratory, Säumerstrasse 4, Ch-8803 Rüschlikon, Switzerland

Keywords: Factoring, polynomials, finite fields, randomized algorithms, normal bases
Received by editor(s): October 12, 1995
Received by editor(s) in revised form: March 29, 1996
Additional Notes: This material is based on work supported in part by the National Science Foundation under Grant No. CCR-9319776 (first author) and by an Alexander von Humboldt Research Fellowship (second author).
A major part of the work was performed while the first author was at Rensselaer Polytechnic Institute, Department of Computer Science, in Troy, New York and while the second author was at the Universität des Saarlandes, FB 14–Informatik, in Saarbrücken, Germany.
A preliminary version of this paper appears in the Proc. 27th Annual ACM Symp. Theory of Computing, ACM Press, pp. 398–406 (1995).
Article copyright: © Copyright 1998 American Mathematical Society

American Mathematical Society