×

zbMATH — the first resource for mathematics

Subquadratic-time factoring of polynomials over finite fields. (English) Zbl 0902.11053
Efficiently factoring univariate polynomials over finite fields is a very important step in the solution of many discrete problems. The first random polynomial-time algorithm for such a factorization was given by E. R. Berlekamp [Math. Comput. 24(1970), 713-735 (1971; Zbl 0247.12014)]. About a decade later a very different approach was suggested by D. G. Cantor and H. Zassenhaus [Math. Comput. 36, 587-592 (1981; Zbl 0493.12024)]. In this latter approach the algorithm starts with a polynomial assumed to be square-free, separates the irreducible factors of distinct degrees, and then completely factors each of the resulting factors. A number of other researchers, including both authors, have improved these techniques over the years.
In the paper under review the authors use the basic Cantor/Zassenhaus strategy to develop a probabilistic approach that factors a polynomial of degree \(n\) over the finite field \(F_q\) (\(q\) being held constant) in \( O(n^{1.815})\) time. This bound is proven by using the result of D. Coppersmith and S. Winograd [J. Symb. Comput. 9, 251-280 (1990; Zbl 0702.65046)] that one can multiply two \(n \times n\) matrices using only \(O(n^\omega)\) arithmetic operations, where \(\omega < 2.375477\). The main technical contribution is a subquadratic distinct-degree factorization algorithm based on the so-called baby step/giant step strategy. The authors also develop a subquadratic algorithm for finding a normal basis of \(F_{q^n}\) over its subfield \(F_q\). Since the algorithms discussed rely on fast multiplication of large matrices, as stated they are not particularly practical. However, the techniques can be adapted to give a practical algorithm that seems to factor larger polynomials (in a reasonable amount of time and space) than previously possible. To achieve the subquadratic running time, randomization is of course used. It remains an open problem to find a subquadratic deterministic algorithm.

MSC:
11Y16 Number-theoretic algorithms; complexity
11T06 Polynomials over finite fields
68W30 Symbolic computation and algebraic computation
13P05 Polynomials, factorization in commutative rings
12E20 Finite fields (field-theoretic aspects)
12Y05 Computational aspects of field theory and polynomials (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0326.68005
[2] Walter Baur and Volker Strassen, The complexity of partial derivatives, Theoret. Comput. Sci. 22 (1983), no. 3, 317 – 330. · Zbl 0498.68028 · doi:10.1016/0304-3975(83)90110-X · doi.org
[3] Ben-Or, M., Probabilistic algorithms in finite fields, Proc. 22nd IEEE Symp. Foundations Comp. Sci., 394-398, 1981.
[4] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713 – 735. · Zbl 0247.12014
[5] 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. · Zbl 0475.65018 · doi:10.1016/0196-6774(80)90013-9 · doi.org
[6] R. P. Brent and H. T. Kung, Fast algorithms for manipulating formal power series, J. Assoc. Comput. Mach. 25 (1978), no. 4, 581 – 595. · Zbl 0388.68052 · doi:10.1145/322092.322099 · doi.org
[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] David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693 – 701. · Zbl 0766.68055 · doi:10.1007/BF01178683 · doi.org
[9] David G. Cantor and Hans Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), no. 154, 587 – 592. · Zbl 0493.12024
[10] D. Coppersmith, Rapid multiplication of rectangular matrices, SIAM J. Comput. 11 (1982), no. 3, 467 – 471. , https://doi.org/10.1137/0211037 D. Coppersmith and S. Winograd, On the asymptotic complexity of matrix multiplication, SIAM J. Comput. 11 (1982), no. 3, 472 – 492. · Zbl 0486.68030 · doi:10.1137/0211038 · doi.org
[11] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251 – 280. · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2 · doi.org
[12] Jean-Louis Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms, IEEE Trans. Inform. Theory 33 (1987), no. 3, 428 – 431. · Zbl 0633.94019 · doi:10.1109/TIT.1987.1057299 · doi.org
[13] 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.
[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] Peter Fleischmann, Connections between the algorithms of Berlekamp and Niederreiter for factoring polynomials over \?_\?, Linear Algebra Appl. 192 (1993), 101 – 108. Computational linear algebra in algebraic and related problems (Essen, 1992). · Zbl 0845.11041 · doi:10.1016/0024-3795(93)90238-J · doi.org
[16] Joachim von zur Gathen and Mark Giesbrecht, Constructing normal bases in finite fields, J. Symbolic Comput. 10 (1990), no. 6, 547 – 570. · Zbl 0718.11065 · doi:10.1016/S0747-7171(08)80158-7 · doi.org
[17] Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187 – 224. · Zbl 0778.11076 · doi:10.1007/BF01272074 · doi.org
[18] Giesbrecht, M., Nearly optimal algorithms for canonical matrix forms, Ph.D. Thesis, Dept. Comput. Science, University of Toronto, Toronto, Canada, 1993. · Zbl 0839.65043
[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. · Zbl 0978.68792
[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] 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. · Zbl 0653.65032 · doi:10.1016/0196-6774(88)90026-0 · doi.org
[23] Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. · Zbl 0477.65002
[24] 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. · Zbl 0864.11063
[25] Seppo Linnainmaa, Taylor expansion of the accumulated rounding error, Nordisk Tidskr. Informationsbehandling (BIT) 16 (1976), no. 2, 146 – 160. · Zbl 0332.65024
[26] Grazia Lotti and Francesco Romani, On the asymptotic complexity of rectangular matrix multiplication, Theoret. Comput. Sci. 23 (1983), no. 2, 171 – 185. · Zbl 0503.68029 · doi:10.1016/0304-3975(83)90054-3 · doi.org
[27] James L. Massey, Shift-register synthesis and \?\?\? decoding, IEEE Trans. Information Theory IT-15 (1969), 122 – 127. · Zbl 0167.18101
[28] Harald Niederreiter, A new efficient factorization algorithm for polynomials over small finite fields, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 81 – 87. · Zbl 0776.11070 · doi:10.1007/BF01386831 · doi.org
[29] Harald Niederreiter and Rainer Göttfert, Factorization of polynomials over finite fields and characteristic sequences, J. Symbolic Comput. 16 (1993), no. 5, 401 – 412. · Zbl 0797.11091 · doi:10.1006/jsco.1993.1055 · doi.org
[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. · Zbl 0228.65016
[31] Michael O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9 (1980), no. 2, 273 – 280. · Zbl 0461.12012 · doi:10.1137/0209024 · doi.org
[32] Štefan Schwarz, On the reducibility of polynomials over a finite field, Quart. J. Math. Oxford Ser. (2) 7 (1956), 110 – 124. · Zbl 0071.01703 · doi:10.1093/qmath/7.1.110 · doi.org
[33] Victor Shoup, On the deterministic complexity of factoring polynomials over finite fields, Inform. Process. Lett. 33 (1990), no. 5, 261 – 267. · Zbl 0696.68072 · doi:10.1016/0020-0190(90)90195-4 · doi.org
[34] Victor Shoup, Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput. 17 (1994), no. 5, 371 – 391. · Zbl 0815.11059 · doi:10.1006/jsco.1994.1025 · doi.org
[35] Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363 – 397. · Zbl 0854.11074 · doi:10.1006/jsco.1995.1055 · doi.org
[36] Douglas H. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory 32 (1986), no. 1, 54 – 62. · Zbl 0607.65015 · doi:10.1109/TIT.1986.1057137 · doi.org
[37] Bürgisser, P., Clausen, M. and Shokrollahi, M. A., Algebraic Complexity Theory, Springer-Verlag, Heidelberg, Germany, 1997. CMP 97:10 · Zbl 1087.68568
[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. · Zbl 0917.65042
[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. · Zbl 0920.11082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.