Subquadratic-time factoring of polynomials over finite fields

Kaltofen, Erich; Shoup, Victor

doi:10.1090/S0025-5718-98-00944-2

Subquadratic-time factoring of polynomials over finite fields
HTML articles powered by AMS MathViewer

by Erich Kaltofen and Victor Shoup PDF

Math. Comp. 67 (1998), 1179-1197 Request permission

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

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
Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317–330. MR 693063, DOI 10.1016/0304-3975(83)90110-X
Ben-Or, M., Probabilistic algorithms in finite fields, Proc. 22nd IEEE Symp. Foundations Comp. Sci., 394–398, 1981.
E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
Richard P. Brent, Fred G. Gustavson, and David Y. Y. Yun, Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms 1 (1980), no. 3, 259–295. MR 604867, DOI 10.1016/0196-6774(80)90013-9
R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581–595. MR 520733, DOI 10.1145/322092.322099
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.
David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587–592. MR 606517, DOI 10.1090/S0025-5718-1981-0606517-5
D. Coppersmith, Rapid multiplication of rectangular matrices, SIAM J. Comput. 11 (1982), no. 3, 467–471. MR 664714, DOI 10.1137/0211037
Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2
Jean-Louis Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms, IEEE Trans. Inform. Theory 33 (1987), no. 3, 428–431. MR 885401, DOI 10.1109/TIT.1987.1057299
Charles M. Fiduccia, On obtaining upper bounds on the complexity of matrix multiplication, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 31–40, 187–212. MR 0391577
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.
Peter Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over $\textbf {F}_q$, Linear Algebra Appl. 192 (1993), 101–108. Computational linear algebra in algebraic and related problems (Essen, 1992). MR 1236738, DOI 10.1016/0024-3795(93)90238-J
Joachim von zur Gathen and Mark Giesbrecht, Constructing normal bases in finite fields, J. Symbolic Comput. 10 (1990), no. 6, 547–570. MR 1087979, DOI 10.1016/S0747-7171(08)80158-7
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Giesbrecht, M., Nearly optimal algorithms for canonical matrix forms, Ph.D. Thesis, Dept. Comput. Science, University of Toronto, Toronto, Canada, 1993.
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.
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.
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.
Michael Kaminski, David G. Kirkpatrick, and Nader H. Bshouty, Addition requirements for matrix and transposed matrix products, J. Algorithms 9 (1988), no. 3, 354–364. MR 955144, DOI 10.1016/0196-6774(88)90026-0
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
Seppo Linnainmaa, Taylor expansion of the accumulated rounding error, Nordisk Tidskr. Informationsbehandling (BIT) 16 (1976), no. 2, 146–160. MR 421065, DOI 10.1007/bf01931367
Grazia Lotti and Francesco Romani, On the asymptotic complexity of rectangular matrix multiplication, Theoret. Comput. Sci. 23 (1983), no. 2, 171–185. MR 699269, DOI 10.1016/0304-3975(83)90054-3
James L. Massey, Shift-register synthesis and $\textrm {BCH}$ decoding, IEEE Trans. Inform. Theory IT-15 (1969), 122–127. MR 242556, DOI 10.1109/tit.1969.1054260
Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81–87. MR 1223850, DOI 10.1007/BF01386831
Harald Niederreiter and Rainer Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. 16 (1993), no. 5, 401–412. MR 1271081, DOI 10.1006/jsco.1993.1055
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.
Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273–280. MR 568814, DOI 10.1137/0209024
Štefan Schwarz, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 7 (1956), 110–124. MR 96679, DOI 10.1093/qmath/7.1.110
Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261–267. MR 1049276, DOI 10.1016/0020-0190(90)90195-4
Victor Shoup, Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput. 17 (1994), no. 5, 371–391. MR 1289997, DOI 10.1006/jsco.1994.1025
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
Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54–62. MR 831560, DOI 10.1109/TIT.1986.1057137
Bürgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, Springer-Verlag, Heidelberg, Germany, 1997.
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.
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.