Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the efficiency of algorithms for polynomial factoring

Author: Robert T. Moenck
Journal: Math. Comp. 31 (1977), 235-250
MSC: Primary 12-04; Secondary 68A10, 68A20
MathSciNet review: 0422193
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Algorithms for factoring polynomials over finite fields are discussed. A construction is shown which reduces the final step of Berlekamp's algorithm to the problem of finding the roots of a polynomial in a finite field $ {Z_p}$.

It is shown that if the characteristic of the field is of the form $ p = L \cdot {2^l} + 1$, where $ l \simeq L$, then the roots of a polynomial of degree n may be found in $ O({n^2}\log p + n{\log ^2}p)$ steps.

As a result, a modification of Berlekamp's method can be performed in $ O({n^3} + {n^2}\log p + n{\log ^2}p)$ steps. If n is very large then an alternative method finds the factors of the polynomial in $ O({n^2}{\log ^2}n + {n^2}\log n\log p)$. Some consequences and empirical evidence are discussed.

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

  • [1] R. H. RISCH, Symbolic Integration of Elementary Functions, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Manipulation, IBM, R. Tobey (Editor), pp. 133-148.
  • [2] B. F. CAVINESS, On Canonical Forms and Simplification, Ph.D. Thesis, Carnegie-Mellon Univ., 1967.
  • [3] D. Y. Y. YUN, "On algorithms for solving systems of polynomial equations," SIGSAM Bull., No. 27, ACM, New York, September 1973.
  • [4] B. L. VAN DER WAERDEN, Modern Algebra, Vol. 1, 2nd rev. ed., Springer, Berlin, 1937; English transl., Ungar, New York, 1949. MR 10, 587.
  • [5] D. JORDAN, R. KAIN & L. CLAPP, "Symbolic factoring of polynomials in several variables," Comm. ACM, v. 9, 1966.
  • [6] D. R. MUSSER, Algorithms for Polynomial Factorization, Ph.D. Thesis, Univ. of Wisconsin, 1971.
  • [7] P. S. WANG & L. P. ROTHSCHILD, "Factoring polynomials over the integers," SIGSAM Bull., No. 28, ACM, New York, December 1973.
  • [8] Elwyn R. Berlekamp, Algebraic coding theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1968. MR 0238597
  • [9] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 0276200,
  • [10] J. D. LIPSON, Chinese Remainder and Interpolation Algorithms, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
  • [11] George E. Collins, Computing multiplicative inverses in 𝐺𝐹(𝑝), Math. Comp. 23 (1969), 197–200. MR 0242345,
  • [12] G. E. COLLINS, Computing Time Analyses of Some Arithmetic and Algebraic Algorithms, Proc. 1968 IBM Summer Inst. on Symbolic and Algebraic Computation.
  • [13] Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR 0286318
  • [14] J. V. USPENSKY, The Theory of Equations, Chap. 11, McGraw-Hill, New York, 1948.
  • [15] George E. Collins, The calculation of multivariate polynomial resultants, J. Assoc. Comput. Mach. 18 (1971), 515–532. MR 0298921,
  • [16] A. Adrian Albert, Fundamental concepts of higher algebra, The University of Chicago Press, Chicago, Ill., 1958. MR 0098735
  • [17] R. T. MOENCK, Studies in Fast Algebraic Algorithms, Ph.D. Thesis, Univ. of Toronto, 1973.
  • [18] Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 0248973,
  • [19] S. GOLOMB, L. WELCH & A. HALES, "On the factorization of trinomials over $ {\text{GF}}(2)$," JPL Memo 20-189 (July 1959)(as referred to in [13]).
  • [20] Volker Strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1972/73), 238–251 (German, with English summary). MR 0324947,
  • [21] Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
  • [22] G. E. COLLINS, The SAC-1 System: An Introduction and Survey, Proc. 2nd SIGSAM Sympos., ACM, New York, 1971.
  • [23] S. C. JOHNSON & R. L. GRAHAM, "Problem #7," SIGSAM Bull., v. 8, No. 1, ACM, New York, February 1974, p. 4.
  • [24] R. FATEMAN, J. MOSES & P. WANG, "Solution to problem #7 using MACSYMA," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 14-16.
  • [25] G. E. COLLINS, D. R. MUSSER & M. ROTHSTEIN, "SAC-1 solution of problem #7," SIGSAM Bull., v. 8, No. 2, ACM, New York, May 1974, pp. 17-19.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 12-04, 68A10, 68A20

Retrieve articles in all journals with MSC: 12-04, 68A10, 68A20

Additional Information

Keywords: Algebraic manipulation, polynomial factoring, roots in finite fields, analysis of algorithms
Article copyright: © Copyright 1977 American Mathematical Society